2026-08-10T22:59:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9987 2024-03-06T10:45:16Z ddc:004 open_access

Polyline Drawings with Topological Constraints Di Giacomo, Emilio Eades, Peter Liotta, Giuseppe Meijer, Henk Montecchiani, Fabrizio Topological graphs graph drawing curve complexity skewness-k graphs k-planar graphs 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 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(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 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Emilio Di Giacomo and Peter Eades and Giuseppe Liotta and Henk Meijer and Fabrizio Montecchiani 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.39 urn:nbn:de:0030-drops-99871 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.39 eng https://creativecommons.org/licenses/by/3.0/legalcode