<div class="csl-bib-body">
<div class="csl-entry">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.), <i>Graph Drawing and Network Visualization. GD 2018</i> (pp. 426–439). Springer. https://doi.org/10.1007/978-3-319-73915-1_33</div>
</div>
-
dc.identifier.isbn
9783319739151
-
dc.identifier.isbn
9783319739144
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/57513
-
dc.description.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
dc.relation.ispartofseries
Lecture Notes in Computer Science
-
dc.title
Planar Drawings of Fixed-Mobile Bigraphs
-
dc.type
Konferenzbeitrag
de
dc.type
Inproceedings
en
dc.relation.isbn
978-3-030-04414-5
-
dc.relation.doi
10.1007/978-3-030-04414-5
-
dc.relation.issn
0302-9743
-
dc.description.startpage
426
-
dc.description.endpage
439
-
dc.type.category
Full-Paper Contribution
-
dc.relation.eissn
1611-3349
-
tuw.booktitle
Graph Drawing and Network Visualization. GD 2018
-
tuw.container.volume
11282
-
tuw.peerreviewed
true
-
tuw.book.ispartofseries
Lecture Notes in Computer Science
-
tuw.relation.publisher
Springer
-
tuw.relation.publisherplace
Cham
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
tuw.publisher.doi
10.1007/978-3-319-73915-1_33
-
dc.description.numberOfPages
14
-
tuw.event.name
26th International Symposium on Graph Drawing and Network Visualization (GD 2018)
-
tuw.event.startdate
26-09-2018
-
tuw.event.enddate
28-09-2018
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Barcelona
-
tuw.event.country
ES
-
tuw.event.presenter
Bekos, Michael A.
-
wb.sciencebranch
Informatik
-
wb.sciencebranch.oefos
1020
-
wb.facultyfocus
Logic and Computation (LC)
de
wb.facultyfocus
Logic and Computation (LC)
en
wb.facultyfocus.faculty
E180
-
wb.presentation.type
science to science/art to art
-
item.openairetype
conference paper
-
item.grantfulltext
none
-
item.fulltext
no Fulltext
-
item.cerifentitytype
Publications
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
crisitem.author.dept
University of Ioannina
-
crisitem.author.dept
Roma Tre University
-
crisitem.author.dept
Utrecht University
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
