In this paper we study the computational complexity of the UPWARD PLANARITY EXTENSION problem, which takes as input an upward planar drawing ΓH of a subgraph H of a directed graph G and asks whether ΓH can be extended to an upward planar drawing of G. Our study fits into the line of research on the extensibility of partial representations, which has recently become a mainstream in Graph Drawing. We show the following results. – First, we prove that the UPWARD PLANARITY EXTENSION problem is NP-complete, even if G has a prescribed upward embedding, the vertex set of H coincides with the one of G, and H contains no edge. – Second, we show that the UPWARD PLANARITY EXTENSION problem can be solved in O(nlog⁡n) time if G is an n-vertex upward planar st-graph. This result improves upon a known O(n2)-time algorithm, which however applies to all n-vertex single-source upward planar graphs. – Finally, we show how to solve in polynomial time a surprisingly difficult version of the UPWARD PLANARITY EXTENSION problem, in which the underlying graph of G is a path or a cycle, G has a prescribed upward embedding, H contains no edges, and no two vertices share the same y-coordinate in ΓH.

Da Lozzo, G., Di Battista, G., Frati, F. (2020). Extending upward planar graph drawings. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 91, 101668 [10.1016/j.comgeo.2020.101668].

Extending upward planar graph drawings

Da Lozzo G.;Di Battista G.;Frati F.
2020

Abstract

In this paper we study the computational complexity of the UPWARD PLANARITY EXTENSION problem, which takes as input an upward planar drawing ΓH of a subgraph H of a directed graph G and asks whether ΓH can be extended to an upward planar drawing of G. Our study fits into the line of research on the extensibility of partial representations, which has recently become a mainstream in Graph Drawing. We show the following results. – First, we prove that the UPWARD PLANARITY EXTENSION problem is NP-complete, even if G has a prescribed upward embedding, the vertex set of H coincides with the one of G, and H contains no edge. – Second, we show that the UPWARD PLANARITY EXTENSION problem can be solved in O(nlog⁡n) time if G is an n-vertex upward planar st-graph. This result improves upon a known O(n2)-time algorithm, which however applies to all n-vertex single-source upward planar graphs. – Finally, we show how to solve in polynomial time a surprisingly difficult version of the UPWARD PLANARITY EXTENSION problem, in which the underlying graph of G is a path or a cycle, G has a prescribed upward embedding, H contains no edges, and no two vertices share the same y-coordinate in ΓH.
Da Lozzo, G., Di Battista, G., Frati, F. (2020). Extending upward planar graph drawings. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 91, 101668 [10.1016/j.comgeo.2020.101668].
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/375894
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 0
social impact