Record link: 
http://hdl.handle.net/20.500.12708/57513
-
Title: 
Planar Drawings of Fixed-Mobile Bigraphs
-
Citation: 
Bekos, M. A., De Luca, F., Didimo, W., Mchedlidze, T., Nöllenburg, M., Symvonis, A., & Tollis, I. G. (2018). Planar Drawings of Fixed-Mobile Bigraphs. In F. Frati & K.-L. Ma (Eds.), Graph Drawing and Network Visualization. GD 2018 (pp. 426–439). Springer. https://doi.org/10.1007/978-3-319-73915-1_33
-
Publisher DOI: 
10.1007/978-3-319-73915-1_33
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Authors: 
Bekos, Michael A. 
De Luca, Felice 
Didimo, Walter 
Mchedlidze, Tamara 
Nöllenburg, Martin 
Symvonis, Antonios 
Tollis, Ioannis G. 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Published in: 
Graph Drawing and Network Visualization. GD 2018 
-
ISBN: 
978-3-030-04414-5
-
Volume: 
11282
-
DOI of the book: 
10.1007/978-3-030-04414-5
-
Date (published): 
2018
-
Event name: 
26th International Symposium on Graph Drawing and Network Visualization (GD 2018) 
-
Event date: 
26-Sep-2018 - 28-Sep-2018
-
Event place: 
Barcelona, Spain
-
Number of Pages: 
14
-
Publisher: 
Springer, Cham
-
Peer reviewed: 
Yes
-
Abstract: 
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.
en
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
Informatik
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

119
checked on Nov 23, 2023

Google ScholarTM

Check