DROPS

Document

DOI: 10.4230/LIPIcs.GD.2024.38

Harborth’s Conjecture for 4-Regular Planar Graphs

Authors: Daniel J. Chang and Timothy Sun

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract

We show that every 4-regular planar graph has a straight-line embedding in the plane where all edges have integer length. The construction extends earlier ideas for finding such embeddings for 4-regular planar graphs with diamond subgraphs or small edge cuts.

Cite as

Daniel J. Chang and Timothy Sun. Harborth’s Conjecture for 4-Regular Planar Graphs. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 38:1-38:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.GD.2024.38,
  author =	{Chang, Daniel J. and Sun, Timothy},
  title =	{{Harborth’s Conjecture for 4-Regular Planar Graphs}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{38:1--38:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.38},
  URN =		{urn:nbn:de:0030-drops-213227},
  doi =		{10.4230/LIPIcs.GD.2024.38},
  annote =	{Keywords: Planar graph, straight-line embedding, Diophantine equation}
}

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.37

Sample-Based High-Dimensional Convexity Testing

Authors: Xi Chen, Adam Freilich, Rocco A. Servedio, and Timothy Sun

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract

In the problem of high-dimensional convexity testing, there is an unknown set S in the n-dimensional Euclidean space which is promised to be either convex or c-far from every convex body with respect to the standard multivariate normal distribution. The job of a testing algorithm is then to distinguish between these two cases while making as few inspections of the set S as possible. In this work we consider sample-based testing algorithms, in which the testing algorithm only has access to labeled samples (x,S(x)) where each x is independently drawn from the normal distribution. We give nearly matching sample complexity upper and lower bounds for both one-sided and two-sided convexity testing algorithms in this framework. For constant c, our results show that the sample complexity of one-sided convexity testing is exponential in n, while for two-sided convexity testing it is exponential in the square root of n.

Cite as

Xi Chen, Adam Freilich, Rocco A. Servedio, and Timothy Sun. Sample-Based High-Dimensional Convexity Testing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.APPROX-RANDOM.2017.37,
  author =	{Chen, Xi and Freilich, Adam and Servedio, Rocco A. and Sun, Timothy},
  title =	{{Sample-Based High-Dimensional Convexity Testing}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{37:1--37:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.37},
  URN =		{urn:nbn:de:0030-drops-75867},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.37},
  annote =	{Keywords: Property testing, convexity, sample-based testing}
}

Search Results

Documents authored by Sun, Timothy

Harborth’s Conjecture for 4-Regular Planar Graphs

Abstract

Cite as

Sample-Based High-Dimensional Convexity Testing

Abstract

Cite as

Thanks for your feedback!

Could not send message