Movatterモバイル変換

[0]ホーム
URL:

Skip to main content
Springer Nature Link
Log in

Every Collinear Set in a Planar Graph is Free

  • Published:
Discrete & Computational Geometry Aims and scope Submit manuscript

Abstract

We show that if a planar graphG has a plane straight-line drawing in which a subsetS of its vertices are collinear, then for any set of points,X, in the plane with\(|X|=|S|\), there is a plane straight-line drawing ofG in which the vertices inS are mapped to the points inX. This solves an open problem posed by Ravsky and Verbitsky (in: Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science,arXiv:0806.0253). In their terminology, we show that every collinear set is free. This result has applications in graph drawing, including untangling, column planarity, universal point subsets, and partial simultaneous drawings.

This is a preview of subscription content,log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

Notes

  1. Ravsky and Verbitsky use a somewhat stronger definition of free collinear set that we call a collinear sequence. This difference is discussed below, after the statement of Theorem 1.1.

References

  1. Angelini, P., Binucci, C., Evans, W., Hurtado, F., Liotta, G., Mchedlidze, T., Meijer, H., Okamoto, Y.: Universal point subsets for planar graphs. In: Chao, K.-M., Hsu, T., Lee, D.-T. (eds.) 23rd International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 7676, pp. 423–432. Springer, Berlin (2012)

  2. Bannister, M.J., Cheng, Z., Devanny, W.E., Eppstein, D.: Superpatterns and universal point sets. J. Graph Algorithms Appl.18(2), 177–209 (2014)

    Article MathSciNet  Google Scholar 

  3. Barba, L., Evans, W., Hoffmann, M., Kusters, V., Saumell, M., Speckmann, B.: Column planarity and partially-simultaneous geometric embedding. J. Graph Algorithms Appl.21(6), 983–1002 (2017)

    Article MathSciNet  Google Scholar 

  4. Bose, P.: On embedding an outer-planar graph in a point set. Comput. Geom.23(3), 303–312 (2002)

    Article MathSciNet  Google Scholar 

  5. Bose, P., Dujmović, V., Hurtado, F., Langerman, S., Morin, P., Wood, D.R.: A polynomial bound for untangling geometric planar graphs. Discrete Comput. Geom.42(4), 570–585 (2009)

    Article MathSciNet  Google Scholar 

  6. Cano, J., Tóth, Cs.D., Urrutia, J.: Upper bound constructions for untangling planar geometric graphs. SIAM J. Discrete Math.28(4), 1935–1943 (2014)

  7. Castañeda, N., Urrutia, J.: Straight line embeddings of planar graphs on point sets. In: Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG’96), pp. 312–318. Carleton University Press (1996)

  8. Cibulka, J.: Untangling polygons and graphs. Discrete Comput. Geom.43(2), 402–411 (2010)

    Article MathSciNet  Google Scholar 

  9. Da Lozzo, G., Dujmović, V., Frati, F., Mchedlidze, T., Roselli, V.: Drawing planar graphs with many collinear vertices. J. Comput. Geom.9(1), 94–130 (2018)

    MathSciNet MATH  Google Scholar 

  10. de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica10(1), 41–51 (1990)

    Article MathSciNet  Google Scholar 

  11. Devillers, O., Liotta, G., Preparata, F.P., Tamassia, R.: Checking the convexity of polytopes and the planarity of subdivisions. Comput. Geom.11(3–4), 187–208 (1998)

    Article MathSciNet  Google Scholar 

  12. Di Giacomo, E., Didimo, W., Liotta, G., Meijer, H., Wismath, S.K.: Planar and quasi-planar simultaneous geometric embedding. Comput. J.58(11), 3126–3140 (2015)

    Article  Google Scholar 

  13. Dujmović, V.: The utility of untangling. J. Graph Algorithms Appl.21(1), 121–134 (2017)

    Article MathSciNet  Google Scholar 

  14. Fáry, I.: On straight line representions of planar graphs. Acta Sci. Math. (Szeged)11, 229–233 (1948)

    MATH  Google Scholar 

  15. Felsner, S., Rote, G.: On primal-dual circle representations. In: Fineman, J.T., Mitzenmacher, M. (eds.) In: Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA 2019). OpenAccess Series in Informatics (OASIcs), vol. 69, pp. 8:1–8:18. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern (2019)

  16. Goaoc, X., Kratochvíl, J., Okamoto, Y., Shin, C.-S., Spillner, A., Wolff, A.: Untangling a planar graph. Discrete Comput. Geom.42(4), 542–569 (2009)

    Article MathSciNet  Google Scholar 

  17. Gritzmann, P., Mohar, B., Pach, J., Pollack, R.: Embedding a planar triangulation with vertices at specified points (solution to problem e3341). Am. Math. Monthly98, 165–166 (1991)

    Article  Google Scholar 

  18. Kang, M., Pikhurko, O., Ravsky, A., Schacht, M., Verbitsky, O.: Untangling planar graphs from a specified vertex position–hard cases. Discrete Appl. Math.159(8), 789–799 (2011)

    Article MathSciNet  Google Scholar 

  19. Kurowski, M.: A 1.235 lower bound on the number of points needed to draw all\(n\)-vertex planar graphs. Inf. Process. Lett.92(2), 95–98 (2004)

    Article MathSciNet  Google Scholar 

  20. Mchedlidze, T., Radermacher, M., Rutter, I.: Aligned drawings of planar graphs. In: Frati, F., Ma, K.-L. (eds.) 25th International Symposium on Graph Drawing and Network Visualization (GD 2017). Lecture Notes in Computer Science, vol. 10692, pp. 3–16. Springer, Cham (2018)

  21. Owens, P.J.: Non-Hamiltonian simple\(3\)-polytopes whose faces are all\(5\)-gons or\(7\)-gons. Discrete Math.36(2), 227–230 (1981)

    Article MathSciNet  Google Scholar 

  22. Pach, J., Tardos, G.: Untangling a polygon. Discrete Comput. Geom.28(4), 585–592 (2002)

    Article MathSciNet  Google Scholar 

  23. Ravsky, A., Verbitsky, O.: On collinear sets in straight-line drawings. In: Kolman, P., Kratochvíl, J. (eds.) 37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2011). Lecture Notes in Computer Science, vol. 6986, pp. 295–306. Springer, Heidelberg (2011).arXiv:0806.0253

  24. Tutte, W.T.: How to draw a graph. Proc. Lond. Math. Soc.13, 743–768 (1963)

    Article MathSciNet  Google Scholar 

  25. Wood, D.R.: A simple proof of the Fáry–Wagner theorem (2005). CoRR,arXiv:cs/0505047

Download references

Acknowledgements

We are grateful to the organizers and participants for providing a stimulating research environment. The work of VD and PM was partly funded by NSERC. The work of FF was partially supported by MIUR Project “MODE” under PRIN 20157EFM5C, by MIUR Project AHeAD under PRIN 20174LF3T8, and by H2020-MSCA-RISE project 734922, “CONNECT”. The work of DG was partly funded by the ANR project GATO, under contract ANR-16-CE40-0009.

Author information

Authors and Affiliations

  1. Department of Computer Science and Electrical Engineering, University of Ottawa, Ottawa, Canada

    Vida Dujmović

  2. Dipartimento di Ingegneria, Universitá Roma Tre, Rome, Italy

    Fabrizio Frati

  3. LIRMM, Université de Montpellier, CNRS, Montpellier, France

    Daniel Gonçalves

  4. School of Computer Science, Carleton University, Ottawa, Canada

    Pat Morin

  5. Institut für Informatik, Freie Universität Berlin, Berlin, Germany

    Günter Rote

Authors
  1. Vida Dujmović

    You can also search for this author inPubMed Google Scholar

  2. Fabrizio Frati

    You can also search for this author inPubMed Google Scholar

  3. Daniel Gonçalves

    You can also search for this author inPubMed Google Scholar

  4. Pat Morin

    You can also search for this author inPubMed Google Scholar

  5. Günter Rote

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toPat Morin.

Additional information

Editor in Charge: Kenneth Clarkson

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Part of this research was conducted during the 5th and the 6th Workshops on Geometry and Graphs, held at the Bellairs Research Institute, March 5–10, 2017 and March 11–16, 2018. The results in this paper were presented at theACM-SIAM Symposium on Discrete Algorithms (SODA19) and a short version of this paper appears in the SODA19 Conference Proceedings.

Rights and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Dujmović, V., Frati, F., Gonçalves, D.et al. Every Collinear Set in a Planar Graph is Free.Discrete Comput Geom65, 999–1027 (2021). https://doi.org/10.1007/s00454-019-00167-x

Download citation

Keywords

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp