Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Equivalence of Turn-Regularity and Complete Extensions

 
: Esser, Alexander

:
Preprint urn:nbn:de:0011-n-5491486 (299 KByte PDF)
MD5 Fingerprint: bf68e2ca14693708680406261b1dcf9e
Erstellt am: 27.6.2019


Kerren, Andreas (Ed.) ; Institute for Systems and Technologies of Information, Control and Communication -INSTICC-, Setubal:
14th International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications, VISIGRAPP 2019. Proceedings. Vol.3: IVAPP : February 25-27, 2019, in Prague, Czech Republic
SciTePress, 2019
ISBN: 978-989-758-354-4
S.39-47
International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications (VISIGRAPP) <14, 2019, Prague>
International Conference on Information Visualization Theory and Applications (IVAPP) <10, 2019, Prague>
Englisch
Konferenzbeitrag, Elektronische Publikation
Fraunhofer IAIS ()
graph drawing; orthogonal drawing; compaction; turn-regularity; complete extension

Abstract
The aim of the two-dimensional compaction problem is to minimize the total edge length or the area of an orthogonal grid drawing. The coordinates of the vertices and the length of the edges can be altered while all angles and the shape of the drawing have to be preserved. The problem has been shown to be NP-hard. Two commonly used compaction methods are the turn-regularity approach by (Bridgeman et al., 2000) and the approach by (Klau and Mutzel, 1999) considering complete extensions. We formally prove that these approaches are equivalent, i. e. a face of an orthogonal representation is turn-regular if and only if there exists a unique complete extension for the segments bounding this face.

: http://publica.fraunhofer.de/dokumente/N-549148.html