Гіпо теза Шейнермана тепер доведена теорема стверджує що будь який планарний граф є графом перетинів набору відрізків на

Гіпо́теза Шейнермана, тепер доведена теорема, стверджує, що будь-який планарний граф є графом перетинів набору відрізків на площині. Цю гіпотезу сформулював ^[en] у своїй кандидатській дисертації, спираючись на раніший результат, що будь-який планарний граф можна подати як граф перетинів простих кривих на площині. Теорему довели Чалопін і Гонсалвіс.

Приклад

Граф G, показаний нижче ліворуч можна подати як граф перетинів набору відрізків, показаних праворуч. Тут вершини графа G подано відрізками, а ребра графа G подано точками перетинів цих відрізків.

Розвиток

Шейнерман також висловив гіпотезу, що достатньо мати відрізки трьох напрямків для подання розфарбовуваних у 3 кольори графів, а Вест висловив гіпотезу, що, аналогічно, будь-який планарний граф можна подати за допомогою відрізків чотирьох напрямків. Якщо граф подаваний відрізками, що мають тільки k напрямків, і ніякі два відрізки не лежать на одній прямій, граф можна розфарбувати за допомогою k кольорів, по одному кольору на кожен напрямок. Тому, якщо будь-який планарний граф можна подати таким способом тільки з чотирма напрямками відрізків, звідси випливатиме теорема про чотири фарби.

Гартман, Ньюман і Зів, а також Де Фрейсікс, Оссона де Мендез і Пах, довели, що будь-який двочастинний планарний граф можна подати як граф перетинів горизонтальних і вертикальних відрізків (див. про це статтю Чижовича, Кранакіса та Уррутія). Де Кастро, Кобос, Дана і Маркес довели, що будь-який вільний від трикутників планарний граф можна подати як граф перетинів відрізків, що мають усього три напрямки. З їхнього результату випливає теорема Ґрьоча, що вільний від трикутників планарний граф можна розфарбувати в три кольори. Де Фрейсікс і Оссона де Мендез довели, що якщо планарний граф G можна розфарбувати в 4 кольори так, що ніякий розділювальний цикл не використовує всіх чотирьох кольорів, то граф G можна подати як граф перетинів відрізків.

Струнні графи

Докладніше: Струнний граф

Чалопін, Гонсалвіс і Очем довели, що планарні графи знаходяться в класі 1-струн, класі графів перетинів простих кривих на площині, які перетинають одна одну максимум один раз на пару кривих. Цей клас є середнім між графами перетинів відрізків, що з'являються в гіпотезі Шейнермана, і графами перетинів простих кривих без обмежень з результатів Ерліха (зі співавторами). Гіпотезу можна розглядати як узагальнення , яка дає той самий результат, коли криві можуть тільки дотикатися між собою. Доведення гіпотези, яке надали Чалопін і Гонсалвіс базувалося на поліпшенні цього результату.

Примітки

Прізвище німецького походження і німецькою воно має звучати «Шайнерман», проте цей математик зі США.
Scheinerman, 1984.
Ehrlich, Even, Tarjan, 1976.
Chalopin, Gonçalves, 2009.
West, 1991.
Hartman, Newman, Ziv, 1991.
de Fraysseix, Ossona de Mendez, Pach, 1991.
Czyzowicz, Kranakis, Urrutia, 1998.
De Castro, Cobos, Dana, Márquez, 2002.
Grötzsch, 1959.
de Fraysseix, Ossona de Mendez, 2005.
Chalopin, Gonçalves, Ochem, 2007.

Література

De Castro N., Cobos F. J., Dana J. C., Márquez A. Triangle-free planar graphs as segment intersection graphs // . — 2002. — Т. 6, вип. 1 (4 липня). — С. 7–26. — DOI:10.7155/jgaa.00043. з джерела 3 грудня 2008. Процитовано 25 березня 2022.
Chalopin J., Gonçalves D. . — 2009.
Chalopin J., Gonçalves D., Ochem P. Planar graphs are in 1-STRING // Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. — ACM and SIAM, 2007. — С. 609–617.
Czyzowicz J., Kranakis E., Urrutia J. A simple proof of the representation of bipartite planar graphs as the contact graphs of orthogonal straight line segments // . — 1998. — Т. 66, вип. 3 (4 липня). — С. 125–126. — DOI:10.1016/S0020-0190(98)00046-5.
de Fraysseix H., Ossona de Mendez P. Graph Drawing, 12th International Symposium, GD 2004. — Springer-Verlag, 2005. — Т. 3383. — С. 217–227. — (Lecture Notes in Computer Science)
de Fraysseix H., Ossona de Mendez P., Pach J. Representation of planar graphs by segments // Intuitive Geometry. — 1991. — Т. 63 (4 липня). — С. 109–117.
Ehrlich G., Even S., Tarjan R. E. Intersection graphs of curves in the plane // . — 1976. — Т. 21, вип. 1 (4 липня). — С. 8–20. — (Series B). — DOI:10.1016/0095-8956(76)90022-8.
Herbert Grötzsch. Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel // Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe. — 1959. — Т. 8 (4 липня). — С. 109–120.
Hartman I. B.-A., Newman I., Ziv R. On grid intersection graphs // Discrete Mathematics. — 1991. — Т. 87, вип. 1 (4 липня). — С. 41–52. — DOI:10.1016/0012-365X(91)90069-E.
Scheinerman E. R. Intersection Classes and Multiple Intersection Parameters of Graphs. — Princeton University, 1984. — (Ph.D. thesis)
West D. Open problems #2 // SIAM Activity Group Newsletter in Discrete Mathematics. — 1991. — Т. 2, вип. 1 (4 липня). — С. 10–12.

[1] Прізвище німецького походження і німецькою воно має звучати «Шайнерман», проте цей математик зі США.

[FOOTNOTEScheinerman1984-2] Scheinerman, 1984.

[FOOTNOTEEhrlich,_Even,_Tarjan1976-3] Ehrlich, Even, Tarjan, 1976.

[FOOTNOTEChalopin,_Gonçalves2009-4] Chalopin, Gonçalves, 2009.

[FOOTNOTEWest1991-5] West, 1991.

[FOOTNOTEHartman,_Newman,_Ziv1991-6] Hartman, Newman, Ziv, 1991.

[FOOTNOTEde_Fraysseix,_Ossona_de_Mendez,_Pach1991-7] Fraysseix, Ossona de Mendez, Pach, 1991.

[FOOTNOTECzyzowicz,_Kranakis,_Urrutia1998-8] Czyzowicz, Kranakis, Urrutia, 1998.

[FOOTNOTEDe_Castro,_Cobos,_Dana,_Márquez2002-9] De Castro, Cobos, Dana, Márquez, 2002.

[FOOTNOTEGrötzsch1959-10] Grötzsch, 1959.

[FOOTNOTEde_Fraysseix,_Ossona_de_Mendez2005-11] Fraysseix, Ossona de Mendez, 2005.

[FOOTNOTEChalopin,_Gonçalves,_Ochem2007-12] Chalopin, Gonçalves, Ochem, 2007.