On bend-minimized orthogonal drawings of planar 3-graphs
Journal
Leibniz International Proceedings in Informatics, LIPIcs
Journal Volume
77
Pages
291-2915
Date Issued
2017
Author(s)
Chang Y.-J
Abstract
An orthogonal drawing of a graph is a planar drawing where each edge is drawn as a sequence of horizontal and vertical line segments. Finding a bend-minimized orthogonal drawing of a planar graph of maximum degree 4 is NP-hard. The problem becomes tractable for planar graphs of maximum degree 3, and the fastest known algorithm takes O(n5 log n) time. Whether a faster algorithm exists has been a long-standing open problem in graph drawing. In this paper we present an algorithm that takes only ?(n17/7) time, which is a significant improvement over the previous state of the art.
Subjects
Drawing (graphics); Graph theory; Graphic methods; Graph drawing; Maximum degree; Maximum degree 3; Orthogonal drawings; Planar drawing; Planar graph; State of the art; Vertical lines; Computational geometry
Type
conference paper