Universell uppsättning poäng

Olösta problem i matematik : Är storleken på universella punktuppsättningar av plana grafer subkvadratisk?

En universell punktuppsättning av ordningen n är en uppsättning S av punkter i det euklidiska planet med egenskapen att varje plan graf med n hörn har ett rakt kantmönster där alla hörn är belägna i punkter i S .

Gränser för dimensionerna för den universella uppsättningen av punkter

Om n är högst tio finns det en universell uppsättning punkter som har exakt n punkter, men för alla n  ≥ 15 ytterligare punkter krävs [1] .

Vissa författare har visat att en delmängd av ett heltalsgitter med storleken O ( n ) ×  O ( n ) är universell. Freysix, Pach och Pollak [2] visade särskilt att gittret (2 n  − 3) × ( n  − 1) är universellt, medan Schneider [3] reducerade gittret ( n  − 1) × ( n  − 1) till en triangulär delmängd ) med n 2 /2 −  O ( n ) punkter. Genom att modifiera metoden av Freysix, Pach och Schneider, fann Brandenburg [4] en inbäddning av vilken plan graf som helst i en triangulär delmängd av ett gitter som innehåller 4 n 2 /9 punkter. En universell uppsättning punkter i form av ett rektangulärt gitter måste ha en storlek på minst n /3 ×  n /3 [5] , men detta utesluter inte möjligheten att det finns en mindre universell uppsättning punkter av andra typer . De minsta kända universella punktuppsättningarna är inte baserade på gitter, utan är byggda från superscheman ( permutationer som innehåller alla bilder av permutationer av en given storlek). Universella punktsatser konstruerade på detta sätt har storlek n 2 /4 −  O ( n ) [6] .

Freysix, Pach och Pollack [2] visade den första icke-triviala nedre gränsen för storleken av en universell punktmängd i formen n  + Ω(√ n ), medan Chrobak och Karloff [7] visade att den universella punktmängden måste innehålla minst 1,098 n  −  o ( n ) poäng. Kurowski [8] föreslog en ännu starkare gräns 1,235 n  −  o ( n ), vilket förblir den bästa nedre gränsen [9] .

Att stänga gapet mellan kända linjära gränser och kvadratiska övre gränser är fortfarande ett öppet problem [10] .

Särskilda klasser av grafer

Underklasser av plana grafer kan i allmänhet ha mindre universella uppsättningar (punktuppsättningar som tillåter ritning av alla grafer med n hörn med direkta kanter i underklassen) än hela klassen av alla plana grafer, och i många fall finns det universella punkter uppsättningar som har precision n punkter. Till exempel är det lätt att se att varje uppsättning av n punkter i den konvexa positionen (som fungerar som hörn av en konvex polygon) är universell för n ytterplanargrafer för n vertex , och i synnerhet för träd . Mindre uppenbart är att varje uppsättning av n punkter i allmän position (inga tre ligger på samma linje) förblir universella för ytterplanära grafer [11] .

Plana grafer som kan delas upp i kapslade slingor och plana grafer med begränsad vägbredd har en universell uppsättning punkter av nästan linjär storlek [12] [6] . Plana 3-träd har universella punktuppsättningar av storlek O ( n 5/3 ). Samma gräns gäller för parallellsekventiella grafer [13] .

Andra ritstilar

Liksom i fallet med grafritning med raka kanter har universella punktuppsättningar studerats för andra stilar. I de flesta av dessa fall finns det universella punktuppsättningar som har exakt n punkter, och de är baserade på en topologisk bokinbäddning , där hörnen är placerade på en linje i planet, och kanterna är ritade som kurvor som skär detta linje högst en gång. Till exempel är varje uppsättning av n kolinjära punkter universell för ett bågdiagram , där varje kant representeras antingen som en singelhalvcirkel eller som en jämn kurva som bildas av två halvcirklar [14] .

Det kan visas att med ett sådant arrangemang innehåller varje konvex kurva i planet en delmängd av n punkter, vilket är universellt för polylinjemönster med högst ett brott per kant [15] . Denna uppsättning innehåller endast mönstrets hörn, inte brytpunkterna. Större uppsättningar är kända som kan användas för ritningar med streckade linjer, där hörnen och alla brytpunkter är punkter i uppsättningen [16] .

Anteckningar

  1. ↑ Cardinal, Hoffmann, Kusters, 2015 .
  2. ↑ 1 2 de Fraysseix, Pach och Pollack, 1988 .
  3. ↑ Schnyder, 1990 .
  4. ↑ Brandenburg, 2008 .
  5. ↑ Dolev, Leighton, Trickey, 1984 ; Chrobak och Karloff 1989 ; Demaine, O'Rourke, 2002–2012 . En svagare kvadratisk gräns för storleken på det gitter som krävs för plana grafritningar gavs tidigare av Valiant (1981 ).
  6. ↑ 1 2 Bannister, Cheng, Devanny, Eppstein, 2013 .
  7. ↑ Chrobak, Karloff, 1989 .
  8. ↑ Kurowski, 2004 .
  9. ↑ Mondal ( 2012 ) hävdade att Kurowskis bevis var fel, men tog senare (efter en diskussion med Gene Cardinal) tillbaka sitt påstående. Se Kurowskis bevis för en förklaring Arkiverad 15 mars 2017 på Wayback Machine .
  10. ↑ Demaine, O'Rourke, 2002–2012 ; Brandenburg, Eppstein, Goodrich, Kobourov, 2003 ; Mohar, 2007 .
  11. ↑ Gritzmann, Mohar, Pach, Pollack, 1991 .
  12. ↑ Angelini, Di Battista, Kaufmann, Mchedlidze, 2012 .
  13. ↑ Fulek, Toth, 2013 .
  14. ↑ Giordano, Liotta, Mchedlidze, Symvonis, 2007 .
  15. ↑ Everett, Lazard, Liotta, Wismat, 2010 .
  16. ↑ Dujmovic, Evans, Lazard, Lenhart, 2013 .

Litteratur