On embeddability of buses in point sets

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationGraph Drawing and Network Visualization - 23rd International Symposium, GD 2015, Revised Selected Papers
EditorsEmilio Di Giacomo, Anna Lubiw
Number of pages14
ISBN (Print)9783319272603
StatePublished - 2015
Event23rd International Symposium on Graph Drawing and Network Visualization, GD 2015 - Los Angeles, United States
Duration: Sep 24 2015Sep 26 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other23rd International Symposium on Graph Drawing and Network Visualization, GD 2015
Country/TerritoryUnited States
CityLos Angeles

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'On embeddability of buses in point sets'. Together they form a unique fingerprint.

Cite this