Planar Drawings of Fixed-Mobile Bigraphs

Bekos, Michael A. and De Luca, Felice and Didimo, Walter and Mchedlidze, Tamara and Nöllenburg, Martin and Symvonis, Antonios and Tollis, Ioannis G. (2017) Planar Drawings of Fixed-Mobile Bigraphs. In: Graph Drawing and Network Visualization. GD 2017, September 25-27 , pp. 426-439(Official URL:

Full text not available from this repository.


A fixed-mobile bigraph G is a bipartite graph such that the vertices of one partition set are given with fixed positions in the plane and the mobile vertices of the other part, together with the edges, must be added to the drawing. We assume that G is planar and study the problem of finding, for a given k≥0, a planar poly-line drawing of G with at most k bends per edge. In the most general case, we show NP-hardness. For k=0 and under additional constraints on the positions of the fixed or mobile vertices, we either prove that the problem is polynomial-time solvable or prove that it belongs to NP. Finally, we present a polynomial-time testing algorithm for a certain type of “layered” 1-bend drawings. Research in this work started at the Bertinoro Workshop on Graph Drawing 2016. We thank all the participants and in particular S.-H. Hong for useful discussions. We also thank an anonymous reviewer of this research for some valuable comments, and especially for suggesting the idea behind the proof of Theorem 6.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.210 Bends
M Methods > M.600 Planar
P Styles > P.600 Poly-line
P Styles > P.720 Straight-line

Actions (login required)

View Item View Item