TY - GEN
T1 - On embeddability of buses in point sets
AU - Bruckdorfer, Till
AU - Kaufmann, Michael
AU - Kobourov, Stephen G.
AU - Pupyrev, Sergey
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - Set membership of points in the plane can be visualized by connecting corresponding points via graphical features, like paths, trees, polygons, ellipses. In this paper we study the bus embeddability problem (BEP): given a set of colored points we ask whether there exists a planar realization with one horizontal straight-line segment per color, called bus, such that all points with the same color are connected with vertical line segments to their bus. We present an ILP and an FPT algorithm for the general problem. For restricted versions of this problem, such as when the relative order of buses is predefined, or when a bus must be placed above all its points, we provide efficient algorithms. We show that another restricted version of the problem can be solved using 2-stack pushall sorting. On the negative side we prove the NP-completeness of a special case of BEP.
AB - Set membership of points in the plane can be visualized by connecting corresponding points via graphical features, like paths, trees, polygons, ellipses. In this paper we study the bus embeddability problem (BEP): given a set of colored points we ask whether there exists a planar realization with one horizontal straight-line segment per color, called bus, such that all points with the same color are connected with vertical line segments to their bus. We present an ILP and an FPT algorithm for the general problem. For restricted versions of this problem, such as when the relative order of buses is predefined, or when a bus must be placed above all its points, we provide efficient algorithms. We show that another restricted version of the problem can be solved using 2-stack pushall sorting. On the negative side we prove the NP-completeness of a special case of BEP.
UR - http://www.scopus.com/inward/record.url?scp=84951974834&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84951974834&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-27261-0_33
DO - 10.1007/978-3-319-27261-0_33
M3 - Conference contribution
AN - SCOPUS:84951974834
SN - 9783319272603
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 395
EP - 408
BT - Graph Drawing and Network Visualization - 23rd International Symposium, GD 2015, Revised Selected Papers
A2 - Di Giacomo, Emilio
A2 - Lubiw, Anna
PB - Springer-Verlag
T2 - 23rd International Symposium on Graph Drawing and Network Visualization, GD 2015
Y2 - 24 September 2015 through 26 September 2015
ER -