notesum.ai

Published at November 12

A well-separated pair decomposition for low density graphs

cs.CG

Released Date: November 12, 2024

Authors: Joachim Gudmundsson, Sampson Wong

Arxiv: http://arxiv.org/abs/2411.08204v1

Refer to caption

	Useful		Realistic
	Distance oracle	Separator	Experiments	SELG	Grid	Comb	Cross
Planar	✓	✓			✓	✓
Highway dimension	✓					✓	✓
Spanners	✓				✓		✓
Treewidth	✓	✓				✓	✓
Doubling dimension	✓				✓		✓
Skeleton dimension	✓					✓	✓
Disc neighbourhood		✓	✓	✓	✓	✓	✓
Bounded growth			✓	✓	✓	✓	✓
Low density	✓	✓	✓	✓	✓	✓	✓