This paper starts the investigation of a constrained version of the point-set embeddability problem. Let G = (V,E) be a planar graph with n vertices, G′ = (V′,E′) a subgraph of G, and S a set of n distinct points in the plane. We study the problem of computing a point-set embedding of G on S subject to the constraint that G′ is drawn with straight-line edges. Different drawing algorithms are presented that guarantee small curve complexity of the resulting drawing, i.e. a small number of bends per edge. It is proved that: (i) If G′ is an outerplanar graph and S is any set of points in convex position, a point-set embedding of G on S can be computed such that the edges of E ∖ E′ have at most 4 bends each. (ii) If S is any set of points in general position and G′ is a face of G or if it is a simple path, the curve complexity of the edges of E ∖ E′ is at most 8. (iii) If S is in general position and G′ is a set of k disjoint paths, the curve complexity of the edges of E ∖ E′ is O(2^k ).

Constrained Point-set Embeddability of Planar Graphs

DI GIACOMO, Emilio;DIDIMO, WALTER;LIOTTA, Giuseppe;
2009

Abstract

This paper starts the investigation of a constrained version of the point-set embeddability problem. Let G = (V,E) be a planar graph with n vertices, G′ = (V′,E′) a subgraph of G, and S a set of n distinct points in the plane. We study the problem of computing a point-set embedding of G on S subject to the constraint that G′ is drawn with straight-line edges. Different drawing algorithms are presented that guarantee small curve complexity of the resulting drawing, i.e. a small number of bends per edge. It is proved that: (i) If G′ is an outerplanar graph and S is any set of points in convex position, a point-set embedding of G on S can be computed such that the edges of E ∖ E′ have at most 4 bends each. (ii) If S is any set of points in general position and G′ is a face of G or if it is a simple path, the curve complexity of the edges of E ∖ E′ is at most 8. (iii) If S is in general position and G′ is a set of k disjoint paths, the curve complexity of the edges of E ∖ E′ is O(2^k ).
2009
9783642002182
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/11391/143702
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact