×

Faster algorithms for the minimum red-blue-purple spanning graph problem. (English) Zbl 1361.05125

Summary: Consider a set of \(n\) points in the plane, each one of which is colored either red, blue, or purple. A red-blue-purple spanning graph (RBP spanning graph) is a graph whose vertices are the points and whose edges connect the points such that the subgraph induced by the red and purple points is connected, and the subgraph induced by the blue and purple points is connected. The minimum RBP spanning graph problem is to find an RBP spanning graph with minimum total edge length. First we consider this problem for the case when the points are located on a circle. We present an algorithm that solves this problem in \(O(n^2)\) time, improving upon the previous algorithm by a factor of \(\Theta(n)\). Also, for the general case we present an algorithm that runs in \(O(n^5)\) time, improving upon the previous algorithm by a factor of \(\Theta(n)\).

MSC:

05C85 Graph algorithms (graph-theoretic aspects)

Software:

MapSets
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. K. Agarwal, B. Aronov, J. Pach, R. Pollack, and M. Sharir. Quasiplanar graphs have a linear number of edges. Combinatorica, 17(1):1–9, 1997. · Zbl 0880.05050 · doi:10.1007/BF01196127
[2] H. A. Akitaya, M. L”offler, and C. D. T’oth. Multi-colored spanning graphs. In 24th International Symposium on Graph Drawing and Network Visualization (GD), pages 81–93, 2016. · Zbl 1478.68207 · doi:10.1007/978-3-319-50106-2_7
[3] B. Alper, N. Riche, G. Ramos, and M. Czerwinski. Design study of LineSets, a novel set visualization technique. IEEE Transactions on Visualization and Computer Graphics, 17(12):2259–2267, 2011. · doi:10.1109/
[4] B. Alsallakh, L. Micallef, W. Aigner, H. Hauser, S. Miksch, and P. Rodgers. Visualizing sets and set-typed data: State-of-the-art and future challenges. In Eurographics Conference on Visualization (EuroVis), 2014.
[5] R. V. Benson. Euclidean geometry and convexity. McGraw-Hill, 1966. · Zbl 0187.44103
[6] U. Brandes, S. Cornelsen, B. Pampel, and A. Sallaberry. Path-based supports for hypergraphs. J. Discrete Algorithms, 14:248–261, 2012. · Zbl 1247.05235
[7] K. Buchin, M. J. van Kreveld, H. Meijer, B. Speckmann, and K. Verbeek. On planar supports for hypergraphs. J. Graph Algorithms Appl., 15(4):533– 549, 2011. · Zbl 1276.05081 · doi:10.7155/jgaa.00237
[8] C. Collins, G. Penn, and M. S. T. Carpendale. Bubble Sets: Revealing set relations with isocontours over existing visualizations. IEEE Trans. Vis. Comput. Graph., 15(6):1009–1016, 2009. · doi:10.1109/TVCG.2009.122
[9] K. Dinkla, M. J. van Kreveld, B. Speckmann, and M. A. Westenberg. Kelp Diagrams: Point set membership visualization. Computer Graphics Forum, 31(3):875–884, 2012. · doi:10.1111/j.1467-8659.2012.03080.x
[10] A. Efrat, Y. Hu, S. G. Kobourov, and S. Pupyrev. MapSets: Visualizing embedded and clustered graphs. J. Graph Algorithms Appl., 19(2):571–593, 2015. · Zbl 1328.05124 · doi:10.7155/jgaa.00364
[11] F. Hurtado, M. Korman, M. J. van Kreveld, M. L”offler, V. S. Adinolfi, R. I. Silveira, and B. Speckmann. Colored spanning graphs for set visualization. In 21st International Symposium on Graph Drawing, pages 280–291, 2013. · Zbl 1406.68084 · doi:10.1007/978-3-319-03841-4_25
[12] F. Hurtado, M. Korman, M. J. van Kreveld, M. L”offler, V. Sacrist’an, A. Shioura, R. I. Silveira, B. Speckmann, and T. Tokuyama. Colored spanning graphs for set visualization. CoRR, arXiv:1603.00580 [cs.CG], 2016. Also to appear in Comput. Geom., special issue in Memoriam: Ferran Hurtado. · Zbl 1380.05065
[13] M. Kaufmann, M. J. van Kreveld, and B. Speckmann. Subdivision drawings of hypergraphs. In 16th International Symposium on Graph Drawing (GD), pages 396–407, 2008. · Zbl 1213.68462 · doi:10.1007/978-3-642-00219-9_39
[14] D. W. Matula and R. R. Sokal. Properties of Gabriel graphs relevant to geographic variation research and the clustering of points in the plane. Geographical Analysis, 12(3):205–222, 1980. · doi:10.1111/j.1538-4632
[15] W. Meulemans, N. H. Riche, B. Speckmann, B. Alper, and T. Dwyer. KelpFusion: A hybrid set visualization technique. IEEE Transactions on Visualization and Computer Graphics, 19(11):1846–1858, 2013. · doi:10.
[16] A. Schrijver.Combinatorial Optimization - Polyhedra and Efficiency. Springer, 2003. · Zbl 1041.90001
[17] P. Simonetto and D. Auber. Visualise undrawable euler diagrams. In 12th International Conference on Information Visualisation, pages 594– 599, 2008. · doi:10.1109/IV.2008.78
[18] G. Stapleton, P. Rodgers, J. Howse, and L. Zhang. Inductively generating euler diagrams. IEEE Transactions on Visualization and Computer Graphics, 17(1):88–100, 2011. · doi:10.1109/TVCG.2010.28
[19] E. R. Tufte. The Visual Display of Quantitative Information. Graphics Press, Cheshire, CT, USA, 1986. IntroductionProperties of Minimum RBP Spanning GraphsThe Algorithm for Points on a CircleThe Dynamic Programming AlgorithmImproving the Running TimeProof of Theorem 1Preliminary ResultsProof of TheoremThe Algorithm for the General CaseOverview of the Previous AlgorithmImproving the Running TimeConclusions
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.