Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102319
Title: On embeddability of buses in point sets
Authors: Bruckdorfer, T.
Kaufmann, M.
Kobourov, S. G.
Pupyrev, S.
Issue Date: 2015
Publisher: Springer Verlag
Citation: On embeddability of buses in point sets / T. Bruckdorfer, M. Kaufmann, S. G. Kobourov, et al. — DOI 10.1007/978-3-319-27261-0_33 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2015. — Vol. 9411. — P. 395-408.
Abstract: 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. © Springer International Publishing Switzerland 2015.
Keywords: ALGORITHMS
DRAWING (GRAPHICS)
VISUALIZATION
EMBEDDABILITY PROBLEM
FPT ALGORITHMS
GRAPHICAL FEATURES
NEGATIVE SIDES
NP-COMPLETENESS
SET MEMBERSHIP
STRAIGHT-LINE SEGMENTS
VERTICAL LINES
BUSES
URI: http://hdl.handle.net/10995/102319
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84951974834
PURE ID: 568305
bdd66afb-5cda-4f2c-bac7-fa16d82f1a06
ISSN: 3029743
ISBN: 9783319272603
DOI: 10.1007/978-3-319-27261-0_33
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84951974834.pdf432,78 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.