Tegning af grafer i rette vinkler

Tegning i rette vinkler (RAC=ret vinkel krydsning, RAC) af en graf er en tegning, hvor hjørner er repræsenteret af punkter, og kanter er repræsenteret af linjestykker eller polylinjer , højst to kanter skærer hinanden i et punkt, og hvis to kanter skærer hinanden, de skal skære hinanden under rette vinkler .

Den retvinklede tegnestil og navnet "RAC-tegning" for denne stil blev foreslået af Didimo, Eides og Liotta [1] , og denne stil opstod efter opdagelsen af, at det at tegne en graf med et stort skæringspunkt i høje vinkler læser bedre end tegninger med små vinkler [2] . Selv for plane grafer kan krydsning af nogle kanter i rette vinkler betydeligt forbedre nogle karakteristika ved tegningen, såsom areal eller vinkelopløsning [3] .

Eksempler

Den komplette graf K 5 har et RPU-mønster med lige kanter, men det har K 6 ikke. Enhver RPC-tegning med 6 hjørner har maksimalt 14 kanter, og K 6 har 15 kanter, for mange til en RPU-tegning [1] .

En komplet todelt graf Ka , b har et RPC-mønster med linjestykker, hvis og kun hvis min( a , b ) ≤ 2 eller a  +  b  ≤ 7. Hvis min( a , b ) ≤ 2, så er grafen plan , og (ved Faris sætning ) har enhver plan graf et mønster i form af linjestykker uden skæringspunkter. Sådanne tegninger falder automatisk ind i RAC-klassen. Kun to tilfælde er tilbage, graferne K 3,3 og K 3,4 . Billede K 3.4 er vist på figuren. K 3,3 kan fås fra K 3,4 ved at fjerne et toppunkt. Ingen af ​​graferne K 4.4 og K 3.5 har et RPU-mønster [4] .

Ribben og knæk

Hvis en graf med n hjørner har en RPC-repræsentation med segmentkanter, kan den maksimalt have 4n  − 10 kanter. Begrænsningen er stram - der er grafer med en RPC-repræsentation, der har nøjagtigt 4n  − 10 kanter [1] . For tegninger med knækkede kanter afhænger antallet af kanter i grafen af ​​antallet af tilladte brud pr. kant. Grafer, der har RPC-repræsentationer med en eller to knæk pr. kant, har O( n )-kanter. Mere specifikt kan antallet af kanter med et knæk ikke overstige 6,5 n , og med to knæk 74,2 n [5] . Enhver graf har en RPC-repræsentation, hvis tre knæk pr. kant [1] er tilladt .

Relation til 1-planaritet

En graf er 1-plan , hvis den har et mønster med højst et skæring pr. kant. Det er intuitivt klart, at denne begrænsning letter repræsentationen af ​​en graf med kanter, der krydser i rette vinkler, og begrænsningen 4 n  − 10 på antallet af kanter af RPC-repræsentationen med kanter som segmenter er tæt på 4 n  − 8-grænsen af antallet af kanter på 1-plane grafer og tæt på 4 n  − 9 grænsen antallet af kanter i repræsentationen af ​​1-plane grafer med kanter som segmenter. Enhver RPC-repræsentation med 4n  − 10 kanter er 1-plan [6] [7] . Derudover har enhver 1-ydreplanær graf (det vil sige en graf med et skæring pr. kant, hvor alle toppunkter ligger på tegningens ydre flade) en RPC-repræsentation [8] . Der er dog 1-plane grafer med 4 n  − 10 kanter, der ikke har en RPC-repræsentation [6] .

Beregningsmæssig kompleksitet

Problemet med at afgøre, om en RPC-graf har en linjesegmentrepræsentation, er NP-hård [9] , og konstruktionen af ​​en RPC-tegning svarer til en bottom-up plan tegning [10] . Men i det specielle tilfælde af 1-ydreplanære grafer kan en RPC-repræsentation bygges i lineær tid [11] .

Noter

  1. ↑ 1 2 3 4 Didimo, Eades, Liotta, 2009 , s. 206-217.
  2. ↑ Huang, Hong, Eades, 2008 , s. 41-46.
  3. ↑ van Kreveld, 2011 , s. 371-376.
  4. ↑ Didimo, Eades, Liotta, 2010 , s. 687-691.
  5. ↑ Arikushi, Fulek, Keszegh et al., 2012 , s. 169-177.
  6. ↑ 1 2 Eades, Liotta, 2013 , s. 961-969.
  7. ↑ Ackerman, 2014 , s. 104-108.
  8. ↑ Dehkordi, Eades, 2012 , s. 543-557.
  9. ↑ Argyriou, Bekos, Symvonis, 2011 , s. 74-85.
  10. ↑ Angelini, Cittadini, Di Battista et al., 2010 , s. 21-32.
  11. ↑ Auer, Bachmaier, Brandenburg et al., 2013 , s. 107-118.

Litteratur