Dynamic planar embeddings of dynamic graphs

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt

Standard

Dynamic planar embeddings of dynamic graphs. / Holm, Jacob; Rotenberg, Eva.

I: Theory of Computing Systems, Bind 61, Nr. 4, 11.2017, s. 1054-1083.

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt

Harvard

Holm, J & Rotenberg, E 2017, 'Dynamic planar embeddings of dynamic graphs', Theory of Computing Systems, bind 61, nr. 4, s. 1054-1083. https://doi.org/10.1007/s00224-017-9768-7

APA

Holm, J., & Rotenberg, E. (2017). Dynamic planar embeddings of dynamic graphs. Theory of Computing Systems, 61(4), 1054-1083. https://doi.org/10.1007/s00224-017-9768-7

Vancouver

Holm J, Rotenberg E. Dynamic planar embeddings of dynamic graphs. Theory of Computing Systems. 2017 nov.;61(4):1054-1083. https://doi.org/10.1007/s00224-017-9768-7

Author

Holm, Jacob ; Rotenberg, Eva. / Dynamic planar embeddings of dynamic graphs. I: Theory of Computing Systems. 2017 ; Bind 61, Nr. 4. s. 1054-1083.

Bibtex

@article{20be1c54ee464957a0cd3edbb9890877,
title = "Dynamic planar embeddings of dynamic graphs",
abstract = "We present an algorithm to support the dynamic embedding in the plane of a dynamic graph. An edge can be inserted across a face between two vertices on the face boundary (we call such a vertex pair linkable), and edges can be deleted. The planar embedding can also be changed locally by flipping components that are connected to the rest of the graph by at most two vertices. Given vertices u,v, linkable(u,v) decides whether u and v are linkable in the current embedding, and if so, returns a list of suggestions for the placement of (u,v) in the embedding. For non-linkable vertices u,v, we define a new query, one-flip- linkable(u,v) providing a suggestion for a flip that will make them linkable if one exists. We support all updates and queries in O(log 2 n) time. Our time bounds match those of Italiano et al. for a static (flipless) embedding of a dynamic graph. Our new algorithm is simpler, exploiting that the complement of a spanning tree of a connected plane graph is a spanning tree of the dual graph. The primal and dual trees are interpreted as having the same Euler tour, and a main idea of the new algorithm is an elegant interaction between top trees over the two trees via their common Euler tour.",
keywords = "Data structures, Dynamic data structures, Graph algorithms, Graph embeddings, Graph theory, Planar graphs",
author = "Jacob Holm and Eva Rotenberg",
year = "2017",
month = nov,
doi = "10.1007/s00224-017-9768-7",
language = "English",
volume = "61",
pages = "1054--1083",
journal = "Theory of Computing Systems",
issn = "1432-4350",
publisher = "Springer",
number = "4",

}

RIS

TY - JOUR

T1 - Dynamic planar embeddings of dynamic graphs

AU - Holm, Jacob

AU - Rotenberg, Eva

PY - 2017/11

Y1 - 2017/11

N2 - We present an algorithm to support the dynamic embedding in the plane of a dynamic graph. An edge can be inserted across a face between two vertices on the face boundary (we call such a vertex pair linkable), and edges can be deleted. The planar embedding can also be changed locally by flipping components that are connected to the rest of the graph by at most two vertices. Given vertices u,v, linkable(u,v) decides whether u and v are linkable in the current embedding, and if so, returns a list of suggestions for the placement of (u,v) in the embedding. For non-linkable vertices u,v, we define a new query, one-flip- linkable(u,v) providing a suggestion for a flip that will make them linkable if one exists. We support all updates and queries in O(log 2 n) time. Our time bounds match those of Italiano et al. for a static (flipless) embedding of a dynamic graph. Our new algorithm is simpler, exploiting that the complement of a spanning tree of a connected plane graph is a spanning tree of the dual graph. The primal and dual trees are interpreted as having the same Euler tour, and a main idea of the new algorithm is an elegant interaction between top trees over the two trees via their common Euler tour.

AB - We present an algorithm to support the dynamic embedding in the plane of a dynamic graph. An edge can be inserted across a face between two vertices on the face boundary (we call such a vertex pair linkable), and edges can be deleted. The planar embedding can also be changed locally by flipping components that are connected to the rest of the graph by at most two vertices. Given vertices u,v, linkable(u,v) decides whether u and v are linkable in the current embedding, and if so, returns a list of suggestions for the placement of (u,v) in the embedding. For non-linkable vertices u,v, we define a new query, one-flip- linkable(u,v) providing a suggestion for a flip that will make them linkable if one exists. We support all updates and queries in O(log 2 n) time. Our time bounds match those of Italiano et al. for a static (flipless) embedding of a dynamic graph. Our new algorithm is simpler, exploiting that the complement of a spanning tree of a connected plane graph is a spanning tree of the dual graph. The primal and dual trees are interpreted as having the same Euler tour, and a main idea of the new algorithm is an elegant interaction between top trees over the two trees via their common Euler tour.

KW - Data structures

KW - Dynamic data structures

KW - Graph algorithms

KW - Graph embeddings

KW - Graph theory

KW - Planar graphs

UR - http://www.scopus.com/inward/record.url?scp=85018508772&partnerID=8YFLogxK

U2 - 10.1007/s00224-017-9768-7

DO - 10.1007/s00224-017-9768-7

M3 - Journal article

AN - SCOPUS:85018508772

VL - 61

SP - 1054

EP - 1083

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 4

ER -

ID: 185366150