Publication

Partitioning Complete Geometric Graphs on Dense Point Sets Into Plane Subgraphs

2024

Abstract

A complete geometric graph consists of a set P of n points in the plane, in general position, and all segments (edges) connecting them. It is a well known question of Bose, Hurtado, Rivera-Campo, and Wood, whether there exists a positive constant c < 1, such that every complete geometric graph on n points can be partitioned into at most cn plane graphs (that is, noncrossing subgraphs). We answer this question in the affirmative in the special case where the underlying point set P is dense, which means that the ratio between the maximum and the minimum distances in P is of the order of Theta(root n).

Official source

https://infoscience.epfl.ch/entities/publication/c67f38a5-6aad-4c92-9144-d9e209458013

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

2024

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/c67f38a5-6aad-4c92-9144-d9e209458013

About this result

Related concepts (32)

Geometric graph theory

Geometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geometric graphs, meaning graphs drawn in the Euclidean plane with possibly intersecting straight-line edges, and topological graphs, where the edges are allowed to be arbitrary continuous curves connecting the vertices; thus, it can be described as "the theory of geometric and topological graphs" (Pach 2013).

Cayley graph

In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group, is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cayley), and uses a specified set of generators for the group. It is a central tool in combinatorial and geometric group theory. The structure and symmetry of Cayley graphs makes them particularly good candidates for constructing families of expander graphs.

Dense set

In topology and related areas of mathematics, a subset A of a topological space X is said to be dense in X if every point of X either belongs to A or else is arbitrarily "close" to a member of A — for instance, the rational numbers are a dense subset of the real numbers because every real number either is a rational number or has a rational number arbitrarily close to it (see Diophantine approximation). Formally, is dense in if the smallest closed subset of containing is itself.

Related publications (8)

Partitioning Complete Geometric Graphs on Dense Point Sets Into Plane Subgraphs

Chat with Graph Search

Barriers to the net zero target in personal mobility

Graph Laplacians for Rotation Equivariant Convolutional Neural Networks

Multiple criteria design analysis of a compensation basin to mitigate hydro-pealink