Document Open Access Logo

Lower Bounds for Electrical Reduction on Surfaces

Authors Hsien-Chih Chang, Marcos Cossarini, Jeff Erickson

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.25.pdf
  • Filesize: 1.06 MB
  • 16 pages

Document Identifiers

Author Details

Hsien-Chih Chang
  • Duke University, Durham, USA
Marcos Cossarini
  • Laboratoire d'Analyse et de Mathématiques Appliquées, Université Paris-Est Marne-la-Vallée, Champs-sur-Marne, France
Jeff Erickson
  • University of Illinois at Urbana-Champaign, Champaign, USA

Funding

This work was partially supported by NSF grant CCF-1408763. We also greatly appreciate the support from Labex Bezout.
  • Chang, Hsien-Chih: This work was initiated when the author was affiliated with University of Illinois at Urbana-Champaign, USA.
  • Cossarini, Marcos: This work is initiated when the author was affiliated with Instituto de Matemática Pura e Aplicada, Brazil.

Cite AsGet BibTex

Hsien-Chih Chang, Marcos Cossarini, and Jeff Erickson. Lower Bounds for Electrical Reduction on Surfaces. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.SoCG.2019.25

Abstract

We strengthen the connections between electrical transformations and homotopy from the planar setting - observed and studied since Steinitz - to arbitrary surfaces with punctures. As a result, we improve our earlier lower bound on the number of electrical transformations required to reduce an n-vertex graph on surface in the worst case [SOCG 2016] in two different directions. Our previous Omega(n^{3/2}) lower bound applies only to facial electrical transformations on plane graphs with no terminals. First we provide a stronger Omega(n^2) lower bound when the planar graph has two or more terminals, which follows from a quadratic lower bound on the number of homotopy moves in the annulus. Our second result extends our earlier Omega(n^{3/2}) lower bound to the wider class of planar electrical transformations, which preserve the planarity of the graph but may delete cycles that are not faces of the given embedding. This new lower bound follow from the observation that the defect of the medial graph of a planar graph is the same for all its planar embeddings.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • electrical transformation
  • Delta-Y-transformation
  • homotopy
  • tight
  • defect
  • SPQR-tree
  • smoothings
  • routing set
  • 2-flipping

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Francesca Aicardi. Tree-like curves. In Vladimir I. Arnold, editor, Singularities and Bifurcations, volume 21 of Advances in Soviet Mathematics, pages 1-31. Amer. Math. Soc., 1994. Google Scholar
  2. Dan Archdeacon, Charles J. Colbourn, Isidoro Gitler, and J. Scott Provan. Four-terminal reducibility and projective-planar wye-delta-wye-reducible graphs. J. Graph Theory, 33(2):83-93, 2000. Google Scholar
  3. Vladimir I. Arnold. Plane curves, their invariants, perestroikas and classifications. In Vladimir I. Arnold, editor, Singularities and Bifurcations, volume 21 of Adv. Soviet Math., pages 33-91. Amer. Math. Soc., 1994. Google Scholar
  4. Vladimir I. Arnold. Topological Invariants of Plane Curves and Caustics, volume 5 of University Lecture Series. Amer. Math. Soc., 1994. Google Scholar
  5. Hsien-Chih Chang. Tightening curves and graphs on surfaces. Ph.D. dissertation, University of Illinois at Urbana-Champaign, 2018. Google Scholar
  6. Hsien-Chih Chang and Jeff Erickson. Electrical reduction, homotopy moves, and defect. Preprint, October 2015. URL: http://arxiv.org/abs/1510.00571.
  7. Hsien-Chih Chang and Jeff Erickson. Untangling Planar Curves. In Proc. 32nd Int. Symp. Comput. Geom., volume 51 of Leibniz International Proceedings in Informatics, pages 29:1-29:15, 2016. URL: http://drops.dagstuhl.de/opus/volltexte/2016/5921.
  8. Hsien-Chih Chang and Jeff Erickson. Unwinding Annular Curves and Electrically Reducing Planar Networks. Accepted to Computational Geometry: Young Researchers Forum, Proc. 33rd Int. Symp. Comput. Geom., 2017. Google Scholar
  9. Hsien-Chih Chang, Jeff Erickson, David Letscher, Arnaud de Mesmay, Saul Schleimer, Eric Sedgwick, Dylan Thurston, and Stephan Tillmann. Tightening Curves on Surfaces via Local Moves. Submitted, 2017. Google Scholar
  10. Yves Colin de Verdière, Isidoro Gitler, and Dirk Vertigan. Réseaux électriques planaires II. Comment. Math. Helvetici, 71:144-167, 1996. Google Scholar
  11. Maurits de Graaf and Alexander Schrijver. Characterizing homotopy of systems of curves on a compact surface by crossing numbers. Linear Alg. Appl., 226-228:519-528, 1995. Google Scholar
  12. Maurits de Graaf and Alexander Schrijver. Decomposition of graphs on surfaces. J. Comb. Theory Ser. B, 70:157-165, 1997. Google Scholar
  13. Maurits de Graaf and Alexander Schrijver. Making curves minimally crossing by Reidemeister moves. J. Comb. Theory Ser. B, 70(1):134–156, 1997. Google Scholar
  14. Lino Demasi and Bojan Mohar. Four terminal planar Delta-Wye reducibility via rooted K_2,4 minors. In Proc. 26th Ann. ACM-SIAM Symp. Discrete Algorithms, pages 1728-1742, 2015. Google Scholar
  15. Giuseppe Di Battista and Roberto Tamassia. On-line planarity testing. SIAM J. Comput., 25(5):956-997, 1996. URL: http://dx.doi.org/10.1137/S0097539794280736.
  16. G. V. Epifanov. Reduction of a plane graph to an edge by a star-triangle transformation. Dokl. Akad. Nauk SSSR, 166:19-22, 1966. In Russian. English translation in Soviet Math. Dokl. 7:13-17, 1966. Google Scholar
  17. Chaim Even-Zohar, Joel Hass, Nati Linial, and Tahl Nowik. Invariants of Random Knots and Links. Discrete &Computational Geometry, 56(2):274-314, 2016. URL: http://arxiv.org/abs/1411.3308.
  18. Thomas A. Feo. I. A Lagrangian Relaxation Method for Testing The Infeasibility of Certain VLSI Routing Problems. II. Efficient Reduction of Planar Networks For Solving Certain Combinatorial Problems. PhD thesis, Univ. California Berkeley, 1985. URL: http://search.proquest.com/docview/303364161.
  19. Thomas A. Feo and J. Scott Provan. Delta-wye transformations and the efficient reduction of two-terminal planar graphs. Oper. Res., 41(3):572-582, 1993. Google Scholar
  20. Isidoro Gitler. Delta-wye-delta Transformations: Algorithms and Applications. PhD thesis, Department of Combinatorics and Optimization, University of Waterloo, 1991. Google Scholar
  21. Isidoro Gitler and Feliú Sagols. On terminal delta-wye reducibility of planar graphs. Networks, 57(2):174-186, 2011. Google Scholar
  22. Joel Hass and Peter Scott. Shortening curves on surfaces. Topology, 33(1):25-43, 1994. Google Scholar
  23. Chuichiro Hayashi, Miwa Hayashi, Minori Sawada, and Sayaka Yamada. Minimal unknotting sequences of Reidemeister moves containing unmatched RII moves. J. Knot Theory Ramif., 21(10):1250099 (13 pages), 2012. URL: http://arxiv.org/abs/1011.3963.
  24. Arthur Edwin Kennelly. Equivalence of triangles and three-pointed stars in conducting networks. Electrical World and Engineer, 34(12):413-414, 1899. Google Scholar
  25. Hiroyuki Nakahara and Hiromitsu Takahashi. An Algorithm for the Solution of a Linear system by Δ-Y Transformations. IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, E79-A(7):1079-1088, 1996. Special Section on Multi-dimensional Mobile Information Network. Google Scholar
  26. Max Neumann-Coto. A characterization of shortest geodesics on surfaces. Algebraic &Geometric Topology, 1:349-368, 2001. Google Scholar
  27. Steven D. Noble and Dominic J. A. Welsh. Knot Graphs. J. Graph Theory, 34(1):100-111, 2000. Google Scholar
  28. Michael Polyak. Invariants of curves and fronts via Gauss diagrams. Topology, 37(5):989-1009, 1998. Google Scholar
  29. Alexander Schrijver. Homotopy and crossing of systems of curves on a surface. Linear Alg. Appl., 114-115:157-167, 1989. Google Scholar
  30. Alexander Schrijver. Decomposition of graphs on surfaces and a homotopic circulation theorem. J. Comb. Theory Ser. B, 51(2):161-210, 1991. Google Scholar
  31. Alexander Schrijver. Circuits in graphs embedded on the torus. Discrete Math., 106/107:415-433, 1992. Google Scholar
  32. Alexander Schrijver. On the uniqueness of kernels. J. Comb. Theory Ser. B, 55:146-160, 1992. Google Scholar
  33. Matthias F. M. Stallmann. Using PQ-trees for planar embedding problems. Technical Report NCSU-CSC TR-85-24, Dept. Comput. Sci., NC State Univ., December 1985. URL: https://people.engr.ncsu.edu/mfms/Publications/1985-TR_NCSU_CSC-PQ_Trees.pdf.
  34. Matthias F. M. Stallmann. On counting planar embeddings. Discrete Math., 122:385-392, 1993. Google Scholar
  35. Ernst Steinitz. Polyeder und Raumeinteilungen. Enzyklopädie der mathematischen Wissenschaften mit Einschluss ihrer Anwendungen, III.AB(12):1-139, 1916. Google Scholar
  36. Ernst Steinitz and Hans Rademacher. Vorlesungen über die Theorie der Polyeder: unter Einschluß der Elemente der Topologie, volume 41 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag, 1934. Reprinted 1976. Google Scholar
  37. Peter Guthrie Tait. On Knots I. Proc. Royal Soc. Edinburgh, 28(1):145-190, 1876–7. Google Scholar
  38. Carsten Thomassen. Embeddings of graphs with no short noncontractible cycles. J. Comb. Theory Ser. B, 48(2):155-177, 1990. URL: http://dx.doi.org/10.1016/0095-8956(90)90115-G.
  39. Klaus Truemper. On Whitney’s 2-isomorphism theorem for graphs. Journal of Graph Theory, 4(1):43-49, 1980. Google Scholar
  40. Klaus Truemper. On the delta-wye reduction for planar graphs. J. Graph Theory, 13(2):141-148, 1989. Google Scholar
  41. Klaus Truemper. Matroid Decomposition. Academic Press, 1992. Google Scholar
  42. Donald Wagner. Delta-wye reduction of almost-planar graphs. Discrete Appl. Math., 180:158-167, 2015. Google Scholar
  43. Hassler Whitney. 2-isomorphic graphs. American Journal of Mathematics, 55(1):245-254, 1933. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact