On embeddability of buses in point sets

DOI10.1007/978-3-319-27261-0_33MaRDI QIDQ2959773zbMATH OpenOpenAlexFDO

Authors Till Bruckdorfer, Michael Kaufmann, Stephen G. Kobourov, Sergey Pupyrev

Publication date 10 February 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.06760

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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 emph{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.

Recommendations

• On the Characterization of Plane Bus Graphs
• Planar bus graphs
• Point-set embeddability of 2-colored trees
• Planar embedding of trees on point sets without the general position assumption
• Graph Drawing

Cited in

(1)

• Planar bus graphs

This page was built for publication: On embeddability of buses in point sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2959773)