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.

Didimo, W., Liotta, G., Ortali, G., Patrignani, M. (2020). Optimal Orthogonal Drawings of Planar 3-Graphs in Linear Time. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (pp.806-825) [10.1137/1.9781611975994.49].

Optimal Orthogonal Drawings of Planar 3-Graphs in Linear Time

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.
Scheda breve Scheda completa Scheda completa (DC)
2020
978-1-61197-599-4
Didimo, W., Liotta, G., Ortali, G., Patrignani, M. (2020). Optimal Orthogonal Drawings of Planar 3-Graphs in Linear Time. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (pp.806-825) [10.1137/1.9781611975994.49].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11590/360766`
• ND
• 23
• ND