On Embeddability of Buses in Point SetsBruckdorfer, Till and Kaufmann, Michael and Kobourov, Stephen G. and Pupyrev, Sergey (2015) On Embeddability of Buses in Point Sets. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 2426, 2015 , pp. 395408(Official URL: http://dx.doi.org/10.1007/9783319272610_33). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319272610_33
AbstractSet 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 straightline 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 2stack pushall sorting. On the negative side we prove the NPcompleteness of a special case of BEP.
Actions (login required)
