Di Giacomo, Emilio ;
Eades, Peter ;
Liotta, Giuseppe ;
Meijer, Henk ;
Montecchiani, Fabrizio
Polyline Drawings with Topological Constraints
Abstract
Let G be a simple topological graph and let Gamma be a polyline drawing of G. We say that Gamma 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 crossingfree 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 crossingfree edges of G is not a connected spanning subgraph, the curve complexity may be Omega(sqrt{n}). 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 skewness1 graphs, the curve complexity can be reduced to one, which is a tight bound. We also consider optimal 2plane graphs and discuss tradeoffs between curve complexity and crossing angle resolution of drawings that fully preserve the topology.
BibTeX  Entry
@InProceedings{digiacomo_et_al:LIPIcs:2018:9987,
author = {Emilio Di Giacomo and Peter Eades and Giuseppe Liotta and Henk Meijer and Fabrizio Montecchiani},
title = {{Polyline Drawings with Topological Constraints}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {39:139:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770941},
ISSN = {18688969},
year = {2018},
volume = {123},
editor = {WenLian Hsu and DerTsai Lee and ChungShou Liao},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9987},
URN = {urn:nbn:de:0030drops99871},
doi = {10.4230/LIPIcs.ISAAC.2018.39},
annote = {Keywords: Topological graphs, graph drawing, curve complexity, skewnessk graphs, kplanar graphs}
}
06.12.2018
Keywords: 

Topological graphs, graph drawing, curve complexity, skewnessk graphs, kplanar graphs 
Seminar: 

29th International Symposium on Algorithms and Computation (ISAAC 2018)

Issue date: 

2018 
Date of publication: 

06.12.2018 