We study the following problem: given a planar graph G and a planar drawing (embedding) of a subgraph of G, can such a drawing be extended to a planar drawing of the entire graph G? This problem fits the paradigm of extending a partial solution for a problem to a complete one, which has been studied before in many different settings. Unlike many cases, in which the presence of a partial solution in the input makes an otherwise easy problem hard, we show that the planarity question remains polynomial-time solvable. Our algorithm is based on several combinatorial lemmas, which show that the planarity of partially embedded graphs exhibits the ‘TONCAS’ behavior “the obvious necessary conditions for planarity are also sufficient.” These conditions are expressed in terms of the interplay between (1) the rotation system and containment relationships between cycles and (2) the decomposition of a graph into its connected, biconnected, and triconnected components. This implies that no dynamic programming is needed for a decision algorithm and that the elements of the decomposition can be processed independently. Further, by equipping the components of the decomposition with suitable data structures and by carefully splitting the problem into simpler subproblems, we make our algorithm run in linear time. Finally, we consider several generalizations of the problem, such as minimizing the number of edges of the partial embedding that need to be rerouted to extend it, and argue that they are NP-hard. We also apply our algorithm to the simultaneous graph drawing problem SIMULTANEOUS EMBEDDING WITH FIXED EDGES (SEFE). There we obtain a linear-time algorithm for the case that one of the input graphs or the common graph has a fixed planar embedding.

Angelini, P., DI BATTISTA, G., Frati, F., Jelinek, V., Kratochvil, J., Patrignani, M., et al. (2015). Testing Planarity of Partially Embedded Graphs. ACM TRANSACTIONS ON ALGORITHMS, 11(4) [10.1145/2629341].

Testing Planarity of Partially Embedded Graphs

ANGELINI, PATRIZIO;DI BATTISTA, Giuseppe;FRATI, FABRIZIO;PATRIGNANI, Maurizio;
2015-01-01

Abstract

We study the following problem: given a planar graph G and a planar drawing (embedding) of a subgraph of G, can such a drawing be extended to a planar drawing of the entire graph G? This problem fits the paradigm of extending a partial solution for a problem to a complete one, which has been studied before in many different settings. Unlike many cases, in which the presence of a partial solution in the input makes an otherwise easy problem hard, we show that the planarity question remains polynomial-time solvable. Our algorithm is based on several combinatorial lemmas, which show that the planarity of partially embedded graphs exhibits the ‘TONCAS’ behavior “the obvious necessary conditions for planarity are also sufficient.” These conditions are expressed in terms of the interplay between (1) the rotation system and containment relationships between cycles and (2) the decomposition of a graph into its connected, biconnected, and triconnected components. This implies that no dynamic programming is needed for a decision algorithm and that the elements of the decomposition can be processed independently. Further, by equipping the components of the decomposition with suitable data structures and by carefully splitting the problem into simpler subproblems, we make our algorithm run in linear time. Finally, we consider several generalizations of the problem, such as minimizing the number of edges of the partial embedding that need to be rerouted to extend it, and argue that they are NP-hard. We also apply our algorithm to the simultaneous graph drawing problem SIMULTANEOUS EMBEDDING WITH FIXED EDGES (SEFE). There we obtain a linear-time algorithm for the case that one of the input graphs or the common graph has a fixed planar embedding.
2015
Angelini, P., DI BATTISTA, G., Frati, F., Jelinek, V., Kratochvil, J., Patrignani, M., et al. (2015). Testing Planarity of Partially Embedded Graphs. ACM TRANSACTIONS ON ALGORITHMS, 11(4) [10.1145/2629341].
File in questo prodotto:
File Dimensione Formato  
Angelini et al-Testing Planarity of Partially Embedded Graphs (ACM 2015).pdf

accesso aperto

Descrizione: Articolo principale
Tipologia: Versione Editoriale (PDF)
Licenza: Creative commons
Dimensione 860.36 kB
Formato Adobe PDF
860.36 kB Adobe PDF Visualizza/Apri

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/286687
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 49
  • ???jsp.display-item.citation.isi??? 26
social impact