Vi beskriver ett nytt tillvägagångssätt för klusterbaserad ritning av stora grafer, som får kluster genom att använda binära utrymme partition (BSP) träd. Vi introducerar också en ny BSP-typ nedbrytning, kallas den balanserade proportionen (BAR) träd, som garanterar att de celler som produceras är konvexa och har avgränsade proportioner. Dessutom är träddjupet O(log n), och dess konstruktion tar O(n log n) tid, där n är antalet punkter. Vi visar att BAR trädet kan användas för att rekursivt dela en graf inbäddad i planet i subgrafer av ungefär samma storlek, så att ritningen av varje subgraf har en balanserad proportion. Som ett resultat får vi en representation av en graf som en samling av O(log n) lager, där varje efterföljande lager representerar grafen i en ökande detaljnivå. Den totala körtiden för algoritmen är O(n log n+m+D0(G)), där n och m är antalet hörn och kanter av grafen G, och D0(G) är den tid det tar att få en första inbäddning av G i planet. I synnerhet, om grafen är planar varje lager är en graf ritad med raka linjer och utan korsningar på n×n rutnätet och körtiden minskar till O (n log n).
Alternativt kan geometrisk grafklustring baserad på binära utrymme partitioner också användas för att visa stora grafer, som beskrivs i REF.
Balanced Aspect Ratio Trees and Their Use for Drawing Large Graphs
{'venue': 'J. Graph Algorithms Appl.', 'journal': 'J. Graph Algorithms Appl.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}