Polyline drawings with topological constraints

DOI10.1016/J.TCS.2019.12.016zbMATH Open1436.68232arXiv1809.08111OpenAlexW2995493473WikidataQ126536049 ScholiaQ126536049MaRDI QIDQ2290634FDOQ2290634

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)

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.

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

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

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)

Cites Work

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

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)