Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Planar Straight-Line Realizations of 2-Trees with Prescribed Edge Lengths

  • Conference paper
  • First Online:
Graph Drawing and Network Visualization (GD 2021)

Part of the book series: Lecture Notes in Computer Science ((LNISA,volume 12868))

Included in the following conference series:

Abstract

We study a classic problem introduced thirty years ago by Eades and Wormald. Let \(G=(V,E,\lambda )\) be a weighted planar graph, where \(\lambda : E \rightarrow \mathbb {R}^+\) is a length function. The Fixed Edge-Length Planar Realization problem (FEPR for short) asks whether there exists a planar straight-line realization of G, i.e., a planar straight-line drawing of G where the Euclidean length of each edge \(e \in E\) is \(\lambda (e)\). Cabello, Demaine, and Rote showed that the FEPR problem is -hard, even when \(\lambda \) assigns the same value to all the edges and the graph is triconnected. Since the existence of large triconnected minors is crucial to the known -hardness proofs, in this paper we investigate the computational complexity of the FEPR problem for weighted 2-trees, which are \(K_4\)-minor free. We show its -hardness, even when \(\lambda \) assigns to the edges only up to four distinct lengths. Conversely, we show that the FEPR problem is linear-time solvable when \(\lambda \) assigns to the edges up to two distinct lengths, or when the input has a prescribed embedding. Furthermore, we consider the FEPR problem for weighted maximal outerplanar graphs and prove it to be linear-time solvable if their dual tree is a path, and cubic-time solvable if their dual tree is a caterpillar. Finally, we prove that the FEPR problem for weighted 2-trees is slice-wise polynomial in the length of the longest path.

This research was partially supported by MIUR Project “AHeAD” under PRIN 20174LF3T8, by H2020-MSCA-RISE project 734922 – “CONNECT”, and by Roma Tre University Azione 4 Project “GeoView”.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 69.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 89.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    As in [12], our algorithms adopt the real RAM model, which is customary in computational geometry and supports standard arithmetic operations in constant time.

References

  1. Abel, Z., Demaine, E.D., Demaine, M.L., Eisenstat, S., Lynch, J., Schardl, T.B.: Who needs crossings? Hardness of plane graph rigidity. In: Fekete, S.P., Lubiw, A. (eds.) 32nd International Symposium on Computational Geometry (SoCG 2016). LIPIcs, vol. 51, pp. 3:1–3:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016). https://doi.org/10.4230/LIPIcs.SoCG.2016.3

  2. Alegría, C., Borrazzo, M., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M.: Planar straight-line realizations of 2-trees with prescribed edge lengths. CoRR abs/2108.09483 (2021). https://arxiv.org/abs/2108.09483

  3. Alon, N., Feldheim, O.N.: Drawing outerplanar graphs using three edge lengths. Comput. Geom. 48(3), 260–267 (2015). https://doi.org/10.1016/j.comgeo.2014.10.006

    Article  MathSciNet  MATH  Google Scholar 

  4. Angelini, P., et al.: Anchored drawings of planar graphs. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 404–415. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45803-7_34

    Chapter  Google Scholar 

  5. Angelini, P., et al.: Windrose planarity: embedding graphs with direction-constrained edges. ACM Trans. Algorithms 14(4), 54:1–54:24 (2018). https://doi.org/10.1145/3239561

  6. Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf. Process. Lett. 8(3), 121–123 (1979). https://doi.org/10.1016/0020-0190(79)90002-4

    Article  MathSciNet  MATH  Google Scholar 

  7. de Berg, M., Khosravi, A.: Optimal binary space partitions for segments in the plane. Int. J. Comput. Geom. Appl. 22(3), 187–206 (2012). https://doi.org/10.1142/S0218195912500045

  8. Berger, B., Kleinberg, J.M., Leighton, F.T.: Reconstructing a three-dimensional model with arbitrary errors. J. ACM 46(2), 212–235 (1999). https://doi.org/10.1145/301970.301972

    Article  MathSciNet  MATH  Google Scholar 

  9. Blažej, V., Fiala, J., Liotta, G.: On the edge-length ratio of 2-trees. In: GD 2020. LNCS, vol. 12590, pp. 85–98. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-68766-3_7

    Chapter  Google Scholar 

  10. Borrazzo, M., Frati, F.: On the planar edge-length ratio of planar graphs. J. Comput. Geom. 11(1), 137–155 (2020). https://doi.org/10.20382/jocg.v11i1a6

  11. Brandes, U., Schlieper, B.: Angle and distance constraints on tree drawings. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 54–65. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-70904-6_7

    Chapter  Google Scholar 

  12. Cabello, S., Demaine, E.D., Rote, G.: Planar embeddings of graphs with specified edge lengths. J. Graph Algorithms Appl. 11(1), 259–276 (2007). https://doi.org/10.7155/jgaa.00145

    Article  MathSciNet  MATH  Google Scholar 

  13. Capkun, S., Hamdi, M., Hubaux, J.: GPS-free positioning in mobile ad hoc networks. Clust. Comput. 5(2), 157–167 (2002). https://doi.org/10.1023/A:1013933626682

    Article  Google Scholar 

  14. Chaplick, S.: Recognizing stick graphs with and without length constraints. J. Graph Algorithms Appl. 24(4), 657–681 (2020). https://doi.org/10.7155/jgaa.00524

    Article  MathSciNet  MATH  Google Scholar 

  15. Chazelle, B.: Triangulating a simple polygon in linear time. Discrete Comput. Geom. 6(3), 485–524 (1991). https://doi.org/10.1007/BF02574703

    Article  MathSciNet  MATH  Google Scholar 

  16. Connelly, R.: On generic global rigidity. In: Gritzmann, P., Sturmfels, B. (eds.) Proceedings of a DIMACS Workshop on Applied Geometry And Discrete Mathematics. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 4, pp. 147–156. DIMACS/AMS (1990). https://doi.org/10.1090/dimacs/004/11

  17. Coullard, C.R., Lubiw, A.: Distance visibility graphs. Int. J. Comput. Geom. Appl. 2(4), 349–362 (1992). https://doi.org/10.1142/S0218195992000202

    Article  MathSciNet  MATH  Google Scholar 

  18. Da Lozzo, G., Devanny, W.E., Eppstein, D., Johnson, T.: Square-contact representations of partial 2-trees and triconnected simply-nested graphs. In: Okamoto, Y., Tokuyama, T. (eds.) 28th International Symposium on Algorithms and Computation (ISAAC 2017). LIPIcs, vol. 92, pp. 24:1–24:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017). https://doi.org/10.4230/LIPIcs.ISAAC.2017.24

  19. Deng, T.: On the implementation and refinement of outerplanar graph algorithms. Master’s thesis, University of Windsor, Ontario, Canada (2007)

    Google Scholar 

  20. 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). https://doi.org/10.1016/S0925-7721(98)00039-X

    Article  MathSciNet  MATH  Google Scholar 

  21. Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, Hoboken (1999)

    MATH  Google Scholar 

  22. Di Battista, G., Tamassia, R.: On-line planarity testing. SIAM J. Comput. 25(5), 956–997 (1996). https://doi.org/10.1137/S0097539794280736

    Article  MathSciNet  MATH  Google Scholar 

  23. Di Battista, G., Tamassia, R., Tollis, I.G.: Constrained visibility representations of graphs. Inf. Process. Lett. 41(1), 1–7 (1992). https://doi.org/10.1016/0020-0190(92)90072-4

    Article  MATH  Google Scholar 

  24. Di Giacomo, E., Didimo, W., Liotta, G.: Radial drawings of graphs: Geometric constraints and trade-offs. J. Discrete Algorithms 6(1), 109–124 (2008). https://doi.org/10.1016/j.jda.2006.12.007

    Article  MathSciNet  MATH  Google Scholar 

  25. Di Giacomo, E., Hančl, J., Liotta, Gi.: 2-Colored point-set embeddings of partial 2-trees. In: Uehara, R., Hong, S., Nandy, S.C. (eds.) WALCOM 2021. LNCS, vol. 12635, pp. 247–259. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-68211-8_20

    Chapter  Google Scholar 

  26. Eades, P., Wormald, N.C.: Fixed edge-length graph drawing is NP-hard. Disc. Appl. Math. 28(2), 111–134 (1990). https://doi.org/10.1016/0166-218X(90)90110-X

    Article  MathSciNet  MATH  Google Scholar 

  27. Geelen, J., Guo, A., McKinnon, D.: Straight line embeddings of cubic planar graphs with integer edge lengths. J. Graph Theory 58(3), 270–274 (2008). https://doi.org/10.1002/jgt.20304

    Article  MathSciNet  MATH  Google Scholar 

  28. Goodrich, M.T., Johnson, T.: Low ply drawings of trees and 2-trees. In: Durocher, S., Kamali, S. (eds.) Proceedings of the 30th Canadian Conference on Computational Geometry (CCCG 2018), pp. 2–10 (2018), http://www.cs.umanitoba.ca/%7Ecccg2018/papers/session1A-p1.pdf

  29. Gutwenger, C., Mutzel, P.: A linear time implementation of SPQR-trees. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 77–90. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44541-2_8

    Chapter  Google Scholar 

  30. Hendrickson, B.: Conditions for unique graph realizations. SIAM J. Comput. 21(1), 65–84 (1992). https://doi.org/10.1137/0221008

    Article  MathSciNet  MATH  Google Scholar 

  31. Hendrickson, B.: The molecule problem: exploiting structure in global optimization. SIAM J. Optim. 5(4), 835–857 (1995). https://doi.org/10.1137/0805040

    Article  MathSciNet  MATH  Google Scholar 

  32. Jackson, B., Jordán, T.: Connected rigidity matroids and unique realizations of graphs. J. Comb. Theory, Ser. B 94(1), 1–29 (2005). https://doi.org/10.1016/j.jctb.2004.11.002

  33. Lenhart, W., Liotta, G., Mondal, D., Nishat, R.I.: Planar and plane slope number of partial 2-trees. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 412–423. Springer, Cham (2013). https://doi.org/10.1007/978-3-319-03841-4_36

    Chapter  Google Scholar 

  34. Lubiw, A., Miltzow, T., Mondal, D.: The complexity of drawing a graph in a polygonal region. In: Biedl, T., Kerren, A. (eds.) GD 2018. LNCS, vol. 11282, pp. 387–401. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-04414-5_28

    Chapter  MATH  Google Scholar 

  35. Melkman, A.A.: On-line construction of the convex hull of a simple polyline. Inf. Process. Lett. 25(1), 11–12 (1987). https://doi.org/10.1016/0020-0190(87)90086-X

    Article  MathSciNet  MATH  Google Scholar 

  36. Mitchell, S.L.: Linear algorithms to recognize outerplanar and maximal outerplanar graphs. Inf. Process. Lett. 9(5), 229–232 (1979). https://doi.org/10.1016/0020-0190(79)90075-9

    Article  MathSciNet  MATH  Google Scholar 

  37. Moran, S., Wolfstahl, Y.: One-page book embedding under vertex-neighborhood constraints. SIAM J. Discrete Math. 3(3), 376–390 (1990). https://doi.org/10.1137/0403034

    Article  MathSciNet  MATH  Google Scholar 

  38. Priyantha, N.B., Chakraborty, A., Balakrishnan, H.: The cricket location-support system. In: Pickholtz, R.L., Das, S.K., Cáceres, R., Garcia-Luna-Aceves, J.J. (eds.) 6th Annual International Conference on Mobile Computing and Networking (MOBICOM 2000), pp. 32–43. ACM (2000). https://doi.org/10.1145/345910.345917

  39. Rengarajan, S., Veni Madhavan, C.E.: Stack and queue number of 2-trees. In: Du, D.-Z., Li, M. (eds.) COCOON 1995. LNCS, vol. 959, pp. 203–212. Springer, Heidelberg (1995). https://doi.org/10.1007/BFb0030834

    Chapter  Google Scholar 

  40. Savarese, C., Rabaey, J., Beutel, J.: Location in distributed ad-hoc wireless sensor networks. In: 2001 IEEE International Conference on Acoustics, Speech, and Signal Processing. Proceedings, vol. 4, pp. 2037–2040 (2001). https://doi.org/10.1109/ICASSP.2001.940391

  41. Saxe, J.: Embeddability of Weighted Graphs in K-space is Strongly NP-hard. CMU-CS-80-102, Carnegie-Mellon University, Department of Computer Science, Pittsburgh (1980). https://books.google.it/books?id=vClAGwAACAAJ

  42. Schaefer, M.: Realizability of graphs and linkages. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 461–482. Springer, New York (2013). https://doi.org/10.1007/978-1-4614-0110-0_24

  43. Silveira, R.I., Speckmann, B., Verbeek, K.: Non-crossing paths with geographic constraints. Discret. Math. Theor. Comput. Sci. 21(3), 1–13 (2019). https://doi.org/10.23638/DMTCS-21-3-15

  44. Syslo, M.M.: Characterizations of outerplanar graphs. Discret. Math. 26(1), 47–53 (1979). https://doi.org/10.1016/0012-365X(79)90060-8

    Article  MathSciNet  MATH  Google Scholar 

  45. Tamassia, R.: Constraints in graph drawing algorithms. Constraints Int. J. 3(1), 87–120 (1998). https://doi.org/10.1023/A:1009760732249

    Article  MathSciNet  MATH  Google Scholar 

  46. Wiegers, M.: Recognizing outerplanar graphs in linear time. In: Tinhofer, G., Schmidt, G. (eds.) WG 1986. LNCS, vol. 246, pp. 165–176. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-17218-1_57

    Chapter  Google Scholar 

  47. Yemini, Y.: Some theoretical aspects of position-location problems. In: 20th Annual Symposium on Foundations of Computer Science (FOCS 1979), pp. 1–8. IEEE Computer Society (1979). https://doi.org/10.1109/SFCS.1979.39

Download references

Author information

Authors and Affiliations

  1. Roma Tre University, Rome, Italy

    Carlos Alegría, Manuel Borrazzo, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati & Maurizio Patrignani

Authors
  1. Carlos Alegría
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Manuel Borrazzo
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Giordano Da Lozzo
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Giuseppe Di Battista
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Fabrizio Frati
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Maurizio Patrignani
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Giordano Da Lozzo .

Editor information

Editors and Affiliations

  1. University of Glasgow, Glasgow, UK

    Helen C. Purchase

  2. University of Passau, Passau, Germany

    Ignaz Rutter

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Alegría, C., Borrazzo, M., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M. (2021). Planar Straight-Line Realizations of 2-Trees with Prescribed Edge Lengths. In: Purchase, H.C., Rutter, I. (eds) Graph Drawing and Network Visualization. GD 2021. Lecture Notes in Computer Science(), vol 12868. Springer, Cham. https://doi.org/10.1007/978-3-030-92931-2_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-92931-2_12

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-92930-5

  • Online ISBN: 978-3-030-92931-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation