On Embeddability of Buses in Point Sets

Bruckdorfer, 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 24-26, 2015, Los Angeles, CA, USA , pp. 395-408 (Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_33).

Full text not available from this repository.


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.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.560 Geometry
P Styles > P.540 Planar
Z Theory > Z.250 Geometry
ID Code:1505

Repository Staff Only: item control page


Ada, A., Coggan, M., Marco, P.D., Doyon, A., Flookes, L., Heilala, S., Kim, E., Wing, J.L.O., Préville-Ratelle, L.F., Whitesides, S., Yu, N.: On bus graph realizability. In: Canadian Conference on Computational Geometry, pp. 229–232 (2007)

Alper, B., Riche, N.H., Ramos, G., Czerwinski, M.: Design study of LineSets, a novel set visualization technique. IEEE Trans. Visual. Comput. Graph. 17(12), 2259–2267 (2011)

Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Inform. Process. Lett. 8(3), 121–123 (1979)

Bekos, M.A., Cornelsen, S., Fink, M., Hong, S.-H., Kaufmann, M., Nöllenburg, M., Rutter, I., Symvonis, A.: Many-to-one boundary labeling with backbones. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 244–255. Springer, Heidelberg (2013)

Bóna, M.: A survey of stack-sorting disciplines. Electron. J. Comb. 9(2), 16 (2003)

Bruckdorfer, T., Felsner, S., Kaufmann, M.: On the characterization of plane bus graphs. In: Spirakis, P.G., Serna, M. (eds.) CIAC 2013. LNCS, vol. 7878, pp. 73–84. Springer, Heidelberg (2013)

Bruckdorfer, T., Kaufmann, M., Kobourov, S., Pupyrev, S.: On embeddability of buses in point sets. CoRR abs/​1508.​06760 (2015)

Buchin, K., van Kreveld, M.J., Meijer, H., Speckmann, B., Verbeek, K.: On planar supports for hypergraphs. J. Graph Algorithms Appl. 15(4), 533–549 (2011)

Cabello, S.: Planar embeddability of the vertices of a graph using a fixed point set is NP-hard. J. Graph Algorithms Appl. 10(2), 353–366 (2006)

Chen, H., Qiao, C., Zhou, F., Cheng, C.K.: Refined single trunk tree: A rectilinear Steiner tree generator for interconnect prediction. In: SLIP, pp. 85–89. ACM (2002)

Collins, C., Penn, G., Carpendale, T.: Bubble Sets: Revealing set relations with isocontours over existing visualizations. IEEE Trans. Visual. Comput. Graph. 15(6), 1009–1016 (2009)

Dickerson, M., Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent drawings: Visualizing non-planar diagrams in a planar way. J. Graph Algorithms Appl. 9(1), 31–52 (2005)

Efrat, A., Hu, Y., Kobourov, S.G., Pupyrev, S.: MapSets: visualizing embedded and clustered graphs. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 452–463. Springer, Heidelberg (2014)

Gansner, E.R., Koren, Y.: Improved circular layouts. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 386–398. Springer, Heidelberg (2007)

Garey, M.R., Graham, R.L., Johnson, D.S.: The complexity of computing Steiner minimal trees. SIAM J. Appl. Math. 32(4), 835–859 (1977)

Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32(4), 826–834 (1977)

Gurobi Optimization, I.: Gurobi optimizer reference manual (2015). www.​gurobi.​com

Hurtado, F., Korman, M., van Kreveld, M., Löffler, M., Sacristán, V., Silveira, R.I., Speckmann, B.: Colored spanning graphs for set visualization. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 280–291. Springer, Heidelberg (2013)

Katz, B., Krug, M., Rutter, I., Wolff, A.: Manhattan-geodesic embedding of planar graphs. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 207–218. Springer, Heidelberg (2010)

Klemz, B., Mchedlidze, T., Nöllenburg, M.: Minimum tree supports for hypergraphs and low-concurrency euler diagrams. In: Ravi, R., Gørtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 265–276. Springer, Heidelberg (2014)

Knuth, D.E.: The Art of Computer Programming, Volume 1. Fundamental Algorithms, 3rd edn. Addison Wesley Longman Publishing Co., Inc., Redwood (1997)

Lengauer, T.: VLSI theory. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A), pp. 835–868. Elsevier, Amsterdam (1990)

Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329–343 (1982)

Meulemans, W., Riche, N.H., Speckmann, B., Alper, B., Dwyer, T.: KelpFusion: A hybrid set visualization technique. IEEE Trans. Visual. Comput. Graph. 19(11), 1846–1858 (2013)

Pierrot, A., Rossin, D.: 2-stack pushall sortable permutations. CoRR abs/​1303.​4376 (2013)

Pierrot, A., Rossin, D.: 2-stack sorting is polynomial. In: Mayr, E.W., Portier, N. (eds.) Symposium on Theoretical Aspects of Computer Science. LIPIcs, vol. 25, pp. 614–626. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2014)

Riche, N.H., Dwyer, T.: Untangling Euler diagrams. IEEE Trans. Visual. Comput. Graph. 16(6), 1090–1099 (2010)

Simonetto, P., Auber, D., Archambault, D.: Fully automatic visualisation of overlapping sets. Comput. Graph. Forum 28(3), 967–974 (2009)

Tamassia, R., Tollis, I.G.: A unified approach to visibility representations of planar graphs. Discrete Comput. Geom. 1, 321–341 (1986)