How to draw a planarization

T. Bläsius, M. Radermacher, I. Rutter

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)

Abstract


We study the problem of computing straight-line drawings of non-planar graphs with few crossings. We assume that a crossing-minimization algorithm is applied first, yielding a planarization, i.e., a planar graph with a dummy vertex for each crossing, that fixes the topology of the resulting drawing. We present and evaluate two different approaches for drawing a planarization in such a way that the edges of the input graph are as straight as possible. The first approach is based on the planarity-preserving force-directed algorithm ImPrEd [18], the second approach, which we call Geometric Planarization Drawing, iteratively moves vertices to their locally optimal positions in the given initial drawing.

This work was initiated within the FYS Heuristische Verfahren zur Visualisierung von dynamischen Netzwerken, financially supported by the “Concept for the Future” of KIT within the framework of the German Excellence Initiative. Work was partially supported by grant WA 654/21-1 of the German Research Foundation (DFG).
Original languageEnglish
Title of host publicationSOFSEM 2017: Theory and Practice of Computer Science
Subtitle of host publication43rd International Conference on Current Trends in Theory and Practice of Computer Science, Limerick, Ireland, January 16-20, 2017, Proceedings
EditorsChristel Baier, Mark van den Brand, Johann Eder, Mike Hinchey, Tiziana Margaria, Bernhard Steffen
Place of PublicationDordrecht
PublisherSpringer
Pages295-308
Number of pages14
ISBN (Print)978-3-319-51963-0
DOIs
Publication statusPublished - 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10139 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint Dive into the research topics of 'How to draw a planarization'. Together they form a unique fingerprint.

Cite this