1-Planar Graphs
| Název práce v češtině: | 1-planární grafy |
|---|---|
| Název v anglickém jazyce: | 1-Planar Graphs |
| Klíčová slova: | graf|kreslení grafů|rovinný graf|1-planární graf |
| Klíčová slova anglicky: | graph|graph drawing|planar graph|1-planar graph |
| Akademický rok vypsání: | 2024/2025 |
| Typ práce: | diplomová práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra aplikované matematiky (32-KAM) |
| Vedoucí / školitel: | prof. RNDr. Jan Kratochvíl, CSc. |
| Řešitel: | Bc. Eliška Červenková - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 14.01.2025 |
| Datum zadání: | 15.01.2025 |
| Datum potvrzení stud. oddělením: | 15.01.2025 |
| Datum a čas obhajoby: | 03.06.2025 08:00 |
| Datum odevzdání elektronické podoby: | 30.04.2025 |
| Datum odevzdání tištěné podoby: | 30.04.2025 |
| Datum proběhlé obhajoby: | 03.06.2025 |
| Oponenti: | doc. RNDr. Martin Balko, Ph.D. |
| Zásady pro vypracování |
| Student se seznámí s časopiseckou literaturou o 1-planárních grafech, které mají nakreslení takové, že všechny hrany jsou úsečky stejné délky. Nakreslení je rovinné, pokud se žádné dvě hrany neprotínají. Nakreslení je 1-planární, pokud každá hrana protíná nejvýše jednu jinou hranu. Je známo, že rovinný graf na n vrcholech může mít až 3n-6 hran, ale nikdy více. Podobně pro 1-planární grafy je známo, že mohou mít nejvýše 4n-8 hran [1], tedy o třetinu více než grafy rovinné. Podmínka nakreslení všech hran jako úseček, a navíc stejné délky, však dramaticky mění situaci. Nechť u_0(n) značí největší možný počet hran grafu na n vrcholech, který má takové rovinné nakreslení, a u_1(n) největší počet hran grafu s 1-planárním takovým nakreslením. Je známo, že u_0(n) = [3n-\sqrt{12n-3}] (viz [2], [3] a [4]). V nedávném článku [5] je dokázáno, že u_1(n) je nejvýše 3n-\sqrt[4]{n}/10. Autoři ale současně upozorňují, že nejlepší známá konstrukce pro u_1(n) je stejná jako pro u_0(n), a explicitně vyslovují otázku, zda u_1(n)=u_0(n) neplatí obecně pro každé n.
V rámci diplomové práce se řešitel zaměří na dvě otázky: 1) Platí u_1(n)=u_0(n) pro každé n? a 2) Je možné dokázat lepší horní odhad než u_1(n) < 3n-\sqrt[4]{n}/10? Cílem je alespoň jednu z těchto otázek zodpovědět, případně dokázat jiné relevantní výsledky o 1-planárních grafech. |
| Seznam odborné literatury |
| [1] János Pach, Farhad Shahrokhi, and Mario Szegedy. Applications of the crossing number. In: Proceedings of the tenth annual symposium on Computational geometry, pages 198–202, 1994.
doi:10.1145/177424.177629 [2] Heiko Harborth. Point sets with equal numbers of unit-distant neighbors. Discrete Geometry, pages 12–18, 1981 [3] Heiko Harborth. Match sticks in the plane. In The lighter side of mathematics. Proceedings of the Eugne Strens memorial conference on recreational mathematics and its history, pages 281–288, 1994 [4] Jérémy Lavollée and Konrad Swanepoel. A tight bound for the number of edges of matchstick graphs. Discrete & Computational Geometry, pages 1–15, 2023 [5] Panna Gehér and Géza Tóth. 1-Planar Unit Distance Graphs. In: Proceedings of the 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Article No. 6; pp. 6:1–6:9, LIPIcs 320, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024 |