This paper addresses a long standing, widely studied, open question: Given a planar 3-graph G (i.e., a planar graph with vertex degree at most three), what is the best computational upper bound to compute a bend-minimum planar orthogonal drawing of G in the variable embedding setting? In this setting the algorithm can choose among the exponentially many planar embeddings of G the one that leads to an orthogonal drawing with the minimum number of bends. We answer the question by describing a linear-time algorithm that computes a bend-minimum planar orthogonal drawing of G. Also, if G is not K4, the drawing has at most one bend per edge. The existence of an orthogonal drawing Γ of a planar 3-graph such that Γ has the minimum number of bends and at most one bend per edge was previously unknown.
Optimal orthogonal drawings of planar 3-graphs in linear time
Didimo W.;Liotta G.;Ortali G.;
2020
Abstract
This paper addresses a long standing, widely studied, open question: Given a planar 3-graph G (i.e., a planar graph with vertex degree at most three), what is the best computational upper bound to compute a bend-minimum planar orthogonal drawing of G in the variable embedding setting? In this setting the algorithm can choose among the exponentially many planar embeddings of G the one that leads to an orthogonal drawing with the minimum number of bends. We answer the question by describing a linear-time algorithm that computes a bend-minimum planar orthogonal drawing of G. Also, if G is not K4, the drawing has at most one bend per edge. The existence of an orthogonal drawing Γ of a planar 3-graph such that Γ has the minimum number of bends and at most one bend per edge was previously unknown.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
