Dynamic Planar Embeddings of Dynamic Graphs

Authors Jacob Holm, Eva Rotenberg



PDF
Thumbnail PDF

File

LIPIcs.STACS.2015.434.pdf
  • Filesize: 0.68 MB
  • 13 pages

Document Identifiers

Author Details

Jacob Holm
Eva Rotenberg

Cite AsGet BibTex

Jacob Holm and Eva Rotenberg. Dynamic Planar Embeddings of Dynamic Graphs. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 434-446, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.STACS.2015.434

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 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, 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 will 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
  • dynamic graphs
  • planar embeddings
  • data structures

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Stephen Alstrup, Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Maintaining information in fully dynamic trees with top trees. ACM Transactions on Algorithms, 1(2):243-264, 2005. Google Scholar
  2. Giuseppe Di Battista and Roberto Tamassia. Incremental planarity testing. In FoCS, 1989., pages 436-441. IEEE, 1989. Google Scholar
  3. Giuseppe Di Battista and Roberto Tamassia. On-line planarity testing. SIAM Journal on Computing, 25:956-997, 1996. Google Scholar
  4. David Eppstein. Dynamic generators of topologically embedded graphs. SODA '03, pages 599-608, 2003. Google Scholar
  5. David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Thomas H. Spencer. Separator based sparsification: I. planarity testing and minimum spanning trees. J. CSS, 52(1):3 - 27, 1996. Google Scholar
  6. David Eppstein, Giuseppe F. Italiano, Roberto Tamassia, Robert E. Tarjan, Jeffery R. Westbrook, and Moti Yung. Maintenance of a minimum spanning forest in a dynamic planar graph. J. Algorithms, 13(1):33-54, March 1992. Special issue for 1st SODA. Google Scholar
  7. Greg N. Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Comput., 14(4):781-798, 1985. Google Scholar
  8. Zvi Galil, Giuseppe F. Italiano, and Neil Sarnak. Fully dynamic planarity testing with applications. J. ACM, 46:28-91, 1999. Google Scholar
  9. John Hopcroft and Robert E. Tarjan. Efficient planarity testing. J. ACM, 21(4):549-568, October 1974. Google Scholar
  10. Giuseppe F. Italiano, Johannes A. La Poutré, and Monika H. Rauch. Fully dynamic planarity testing in planar embedded graphs (extended abstract). ESA '93, Proceedings, pages 212-223, 1993. Google Scholar
  11. David R. Karger. Random sampling in cut, flow, and network design problems. Mathematics of Operations Research, pages 648-657, 1994. Google Scholar
  12. Johannes A. La Poutré. Alpha-algorithms for incremental planarity testing (preliminary version). In STOC '94, pages 706-715. ACM, 1994. Google Scholar
  13. Mihai Pătraşcu and Erik D. Demaine. Logarithmic lower bounds in the cell-probe model. SIAM Journal on Computing, 35(4):932-963, 2006. See also STOC'04, SODA'04. Google Scholar
  14. Mihai Pătraşcu and Mikkel Thorup. Planning for fast connectivity updates. In FOCS '07, pages 263-271, 2007. Google Scholar
  15. Jeffery Westbrook. Fast incremental planarity testing. In W. Kuich, editor, ALP, volume 623, pages 342-353. Springer Berlin Heidelberg, 1992. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail