Drawing partially embedded and simultaneously planar graphs

DOI10.1007/978-3-662-45803-7_3MaRDI QIDQ5892028zbMATH OpenOpenAlexFDO

Authors Timothy M. Chan, Fabrizio Frati, Carsten Gutwenger, Anna Lubiw, Petra Mutzel, Marcus Schaefer

Publication date 7 January 2015

Published in Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.8205

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We investigate the problem of constructing planar drawings with few bends for two related problems, the partially embedded graph problem---to extend a straight-line planar drawing of a subgraph to a planar drawing of the whole graph---and the simultaneous planarity problem---to find planar drawings of two graphs that coincide on shared vertices and edges. In both cases we show that if the required planar drawings exist, then there are planar drawings with a linear number of bends per edge and, in the case of simultaneous planarity, a constant number of crossings between every pair of edges. Our proofs provide efficient algorithms if the combinatorial embedding of the drawing is given. Our result on partially embedded graph drawing generalizes a classic result by Pach and Wenger which shows that any planar graph can be drawn with a linear number of bends per edge if the location of each vertex is fixed.

Recommendations

• Drawing partially embedded and simultaneously planar graphs
• Testing Planarity of Partially Embedded Graphs
• Drawing simultaneously embedded graphs with few bends
• Simultaneous Embedding with Two Bends per Edge in Polynomial Area
• Simultaneous embeddings with few bends and crossings

Cited in

(20)

• -stars or on extending a drawing of a connected subgraph
• A Kuratowski-type theorem for planarity of partially embedded graphs
• On the curve complexity of 3-colored point-set embeddings
• Drawing simultaneously embedded graphs with few bends
• Column planarity and partial simultaneous geometric embedding
• Extending convex partial drawings of graphs
• Confluent Drawings: Visualizing Non-planar Diagrams in a Planar Way
• GRIP: Graph Drawing with Intelligent Placement
• Progress on partial edge drawings
• Simultaneous PQ-ordering with applications to constrained embedding problems
• Progress on partial edge drawings
• Column planarity and partially-simultaneous geometric embedding
• A Kuratowski-type theorem for planarity of partially embedded graphs
• Drawing HV-Restricted Planar Graphs
• Testing planarity of partially embedded graphs
• Graph Drawing
• Drawing partially embedded and simultaneously planar graphs
• Drawing Simultaneously Embedded Graphs with Few Bends
• Geometric thickness of multigraphs is \(\exists \mathbb{R}\)-complete
• Drawing two posets

This page was built for publication: Drawing partially embedded and simultaneously planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5892028)