Universelt sæt af punkter

Uløste problemer i matematik : Er størrelsen af ​​universelle punktsæt af plane grafer subkvadratisk?

Et universelt punktsæt af orden n er et sæt S af punkter i det euklidiske plan med den egenskab, at enhver plan graf med n toppunkter har et ligekantsmønster , hvor alle toppunkter er placeret i punkter i S .

Grænser for dimensionerne af det universelle sæt af punkter

Hvis n højst er ti, er der et universelt sæt af punkter, der har præcis n punkter, men for alle n  ≥ 15 yderligere punkter kræves [1] .

Nogle forfattere har vist, at en delmængde af et heltalsgitter med størrelsen O ( n ) ×  O ( n ) er universel. Især Freysix, Pach og Pollak [2] viste, at gitteret (2 n  − 3) × ( n  − 1) er universelt, mens Schneider [3] reducerede gitteret ( n  − 1) × ( n  − 1) til en trekantet delmængde ) med n 2 /2 −  O ( n ) punkter. Ved at modificere metoden fra Freysix, Pach og Schneider, fandt Brandenburg [4] en indlejring af enhver plan graf i en trekantet delmængde af et gitter indeholdende 4 n 2/9 punkter. Et universelt sæt af punkter i form af et rektangulært gitter skal have en størrelse på mindst n /3 ×  n /3 [5] , men dette udelukker ikke muligheden for, at der findes et mindre universelt sæt af punkter af andre typer . De mindste kendte universelle punktsæt er ikke baseret på gitter, men er bygget ud fra superskemaer ( permutationer , der indeholder alle billeder af permutationer af en given størrelse). Universal punktsæt konstrueret på denne måde har størrelse n 2 /4 −  O ( n ) [6] .

Freysix, Pach og Pollack [2] beviste den første ikke-trivielle nedre grænse for størrelsen af ​​et universelt punktsæt i formen n  + Ω(√ n ), mens Chrobak og Karloff [7] viste, at det universelle punktsæt skal indeholde mindst 1.098 n  −  o ( n ) point. Kurowski [8] foreslog en endnu stærkere grænse 1.235 n  −  o ( n ), som forbliver den bedste nedre grænse [9] .

At lukke afstanden mellem kendte lineære grænser og kvadratiske øvre grænser forbliver et åbent problem [10] .

Særlige klasser af grafer

Underklasser af plane grafer kan generelt have mindre universelle sæt (punktsæt, der tillader tegning af alle grafer med n toppunkter med direkte kanter i underklassen) end den fulde klasse af alle plane grafer, og i mange tilfælde er der universelle punkter sæt, der har præcision n punkter. For eksempel er det let at se, at ethvert sæt af n punkter i den konvekse position (som tjener som hjørner af en konveks polygon) er universel for n toppunkt ydreplane grafer , og især for træer . Mindre indlysende forbliver ethvert sæt af n punkter i generel position (ikke tre ligger på samme linje) universelle for ydreplanære grafer [11] .

Plane grafer, der kan opdeles i indlejrede sløjfer og plane grafer med begrænset vejbredde , har et universelt sæt punkter af næsten lineær størrelse [12] [6] . Plane 3-træer har universelle punktsæt af størrelse O ( n 5/3 ). Den samme grænse gælder for parallel-sekventielle grafer [13] .

Andre tegnestile

Som i tilfældet med graftegning med lige kanter, er universelle punktsæt blevet undersøgt for andre stilarter. I de fleste af disse tilfælde er der universelle punktsæt, der har præcis n punkter, og de er baseret på en topologisk bogindlejring , hvor hjørnerne er placeret på en linje i planet, og kanterne er tegnet som kurver, der skærer denne. linje højst én gang. For eksempel er ethvert sæt af n kollineære punkter universelt for et buediagram , hvor hver kant er repræsenteret enten som en enkelt halvcirkel eller som en glat kurve dannet af to halvcirkler [14] .

Det kan vises, at ved brug af et sådant arrangement, indeholder enhver konveks kurve i planet en delmængde af n punkter, hvilket er universelt for polylinjemønstre med højst et brud pr. kant [15] . Dette sæt indeholder kun hjørnerne af mønsteret, ikke brudpunkterne. Der kendes større sæt, der kan bruges til tegninger med stiplede linjer, hvor spidserne og alle knækpunkter er punkter i sættet [16] .

Noter

  1. ↑ Cardinal, Hoffmann, Kusters, 2015 .
  2. ↑ 1 2 de Fraysseix, Pach og Pollack, 1988 .
  3. ↑ Schnyder, 1990 .
  4. ↑ Brandenburg, 2008 .
  5. ↑ Dolev, Leighton, Trickey, 1984 ; Chrobak og Karloff 1989 ; Demaine, O'Rourke, 2002-2012 . En svagere kvadratisk afgrænsning af størrelsen af ​​det gitter, der kræves til plane graftegninger, blev tidligere givet af Valiant (1981 ).
  6. ↑ 1 2 Bannister, Cheng, Devanny, Eppstein, 2013 .
  7. ↑ Chrobak, Karloff, 1989 .
  8. ↑ Kurowski, 2004 .
  9. ↑ Mondal ( 2012 ) hævdede, at Kurowskis bevis var forkert, men trak senere (efter en diskussion med Gene Cardinal) sin påstand tilbage. Se Kurowskis bevis for en forklaring Arkiveret 15. marts 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