The Partial Visibility Representation Extension Problem
For a graph G, a function \(\psi \) is called a bar visibility representation of G when for each vertex \(v \in V(G)\) , \(\psi (v)\) is a horizontal line segment (bar) and \(uv \in E(G)\) iff there is an unobstructed, vertical, \(\varepsilon \) -wide lin
- PDF / 279,459 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 20 Downloads / 169 Views
3
Lehrstuhl f¨ ur Informatik I, Universit¨ at W¨ urzburg, W¨ urzburg, Germany [email protected] 2 Theoretical Computer Science Department, Faculty of Mathematics and Computer Science, Jagiellonian University, Krak´ ow, Poland {guspiel,gutowski,krawczyk}@tcs.uj.edu.pl Dipartimento di Ingegneria, Universit` a degli Studi di Perugia, Perugia, Italy [email protected]
Abstract. For a graph G, a function ψ is called a bar visibility representation of G when for each vertex v ∈ V (G), ψ(v) is a horizontal line segment (bar ) and uv ∈ E(G) iff there is an unobstructed, vertical, ε-wide line of sight between ψ(u) and ψ(v). Graphs admitting such representations are well understood (via simple characterizations) and recognizable in linear time. For a directed graph G, a bar visibility representation ψ of G, additionally, for each directed edge (u, v) of G, puts the bar ψ(u) strictly below the bar ψ(v). We study a generalization of the recognition problem where a function ψ defined on a subset V of V (G) is given and the question is whether there is a bar visibility representation ψ of G with ψ|V = ψ . We show that for undirected graphs this problem together with closely related problems are NP-complete, but for certain cases involving directed graphs it is solvable in polynomial time.
1
Introduction
The concept of a visibility representation of a graph is a classic one in computational geometry and graph drawing and the first studies on this concept date back to the early days of these fields (see, e.g. [16,17] and [12] for a recent survey). This work was partially supported by ESF project EUROGIGA GraDR and preliminary ideas were formed during HOMONOLO 2014. G. Gu´spiel was partially supported by the MNiSW grant DI2013 000443. G. Gutowski was partially supported by the Polish National Science Center grant UMO-2011/03/D/ST6/01370. T. Krawczyk was partially supported by the Polish National Science Center grant UMO-2015/17/B/ST6/01873. G. Liotta was partially supported by the MIUR project AMANDA “Algorithmics for MAssive and Networked DAta”, prot. 2012C4E3KT 001. The full version of this paper is available on arXiv:1512.00174 [5]. Note: whenever we refer to sections in the Appendix we mean the appendix of arXiv:1512.00174v2. c Springer International Publishing AG 2016 Y. Hu and M. N¨ ollenburg (Eds.): GD 2016, LNCS 9801, pp. 266–279, 2016. DOI: 10.1007/978-3-319-50106-2 21
The Partial Visibility Representation Extension Problem
267
In the most general setting, a visibility representation of a graph is defined as a collection of disjoint sets from an Euclidean space such that the vertices are bijectively mapped to the sets and the edges correspond to unobstructed lines of sight between two such sets. Many different classes of visibility representations have been studied via restricting the space (e.g., to be the plane), the sets (e.g., to be points or line segments) and/or the lines of sight (e.g., to be non-crossing or axis-parallel). In this work we focus on a classic visibility representation
Data Loading...
