Polyline drawings with topological constraints

DOI10.1016/J.TCS.2019.12.016MaRDI QIDQ2290634zbMATH OpenOpenAlexWikidataFDO

Authors Emilio Di Giacomo, Peter Eades, Giuseppe Liotta, Fabrizio Montecchiani, Henk Meijer

Publication date 29 January 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.08111, https://drops.dagstuhl.de/opus/volltexte/2018/9987/

zbMATH Keywords

graph drawingtopological graphspolyline drawingstopology constraints

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: Let $G$ be a simple topological graph and let $Gamma$ be a polyline drawing of $G$. We say that $Gamma$ emph{partially preserves the topology} of $G$ if it has the same external boundary, the same rotation system, and the same set of crossings as $G$. Drawing $Gamma$ fully preserves the topology of $G$ if the planarization of $G$ and the planarization of $Gamma$ have the same planar embedding. We show that if the set of crossing-free edges of $G$ forms a connected spanning subgraph, then $G$ admits a polyline drawing that partially preserves its topology and that has curve complexity at most three (i.e., at most three bends per edge). If, however, the set of crossing-free edges of $G$ is not a connected spanning subgraph, the curve complexity may be $Omega(sqrtn)$. Concerning drawings that fully preserve the topology, we show that if $G$ has skewness $k$, it admits one such drawing with curve complexity at most $2k$; for skewness-1 graphs, the curve complexity can be reduced to one, which is a tight bound. We also consider optimal $2$-plane graphs and discuss trade-offs between curve complexity and crossing angle resolution of drawings that fully preserve the topology.

Recommendations

• On the size of graphs that admit polyline drawings with few bends and crossing angles
• Graphs that admit polyline drawings with few crossing angles
• On Planar Polyline Drawings
• Trade-Offs in Planar Polyline Drawings
• Curve-constrained drawings of planar graphs

Cites work

• scientific article; zbMATH DE number 3047038 (Why is no real title available?)
• 2-connected spanning subgraphs of planar 3-connected graphs
• An annotated bibliography on 1-planarity
• Bemerkungen zum Vierfarbenproblem
• Convex Maps
• Drawing plane graphs nicely
• Edge partitions of optimal 2-plane and 3-plane graphs
• Enumeration of simple complete topological graphs
• Graphs drawn with few crossings per edge
• Guest Editors' Foreword and Overview
• How to draw a planarization
• New results on edge partitions of 1-plane graphs
• Noncrossing Subgraphs in Topological Layouts
• On Optimal 2- and 3-Planar Graphs
• Polyline Drawings with Topological Constraints
• Rectilinear drawings of graphs
• Relating graph thickness to planar layers and bend complexity
• Simple realizability of complete abstract topological graphs in P
• Straight-Line Drawability of a Planar Graph Plus an Edge
• Topological morphing of planar graphs

Cited in

(4)

• An annotated review on graph drawing and its applications
• Polyline Drawings with Topological Constraints
• Beyond planar graphs: introduction
• Trade-Offs in Planar Polyline Drawings

This page was built for publication: Polyline drawings with topological constraints

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