Another Wikipedia illustration: empty regions for the Euclidean minimum spanning tree ( If the red vertical segment is to be an MST edge, the outer white lens needs to be empty of other points; this emptiness implies that the edge is part of the relative neighborhood graph. The emptiness of the light blue diameter circle inside the lens defines the Gabriel graph in the same way. The inner rhombus must not only be empty, but disjoint from the rhombi of other edges.

· · Web · 1 · 2 · 3

@11011110 would you be willing to point me to some resources to learn more about these topics? I'm intrigued but don't know much about graph theory. The circles I work with are usually either tangent or orthogonal, but I'm hoping to dive into discrete groups, algebraic interpretations of parallelograms, and cool stuff I encounter while learning about other cool stuff, haha.

Gorgeous illustration, by the way.

I love that the color palette is compatible with works from previous centuries.

@HolomorphicShoes This general area goes under the name "proximity graphs" or "spatial networks". I would like Wikipedia to be that good general reference, but its coverage is not always consistent. Toth's survey is good but telegraphic and technical. An old survey by Toussaint from 1992 might be more readable as a starter.

@11011110 Thanks so much! Super grateful to people who contribute to Wikipedia articles :) I learn so much there.

@11011110 Ha! I just realized the archive article you linked is called
"Relative graphs and their relatives" and am very amused. The explanations are indeed readable, yay, thanks again!

@11011110 and omg, circular lunes!!! I love encountering lunes. A great word for a great shape. Way too excited haha

Sign in to participate in the conversation

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!