Any graph is "drawable" on a 2D surface?

  • Context: Undergrad 
  • Thread starter Thread starter paizhaulski
  • Start date Start date
  • Tags Tags
    2d Graph Surface
Click For Summary

Discussion Overview

The discussion centers around the question of whether any graph can be drawn on a 2D surface and how this relates to the concept of planar graphs. Participants explore the implications of edge crossings and the conditions under which graphs can be represented in a two-dimensional format.

Discussion Character

  • Exploratory, Technical explanation, Debate/contested

Main Points Raised

  • Some participants inquire about formal theorems regarding the drawable nature of any graph on a 2D surface, particularly in relation to pixel mapping with infinitely small pixels.
  • Others suggest that the problem may be trivial if edges are allowed to cross, implying a straightforward proof exists.
  • A participant raises a concern about distinguishing between edges that cross at points not designated as vertices and those that meet at vertices, highlighting the complexity of edge crossings.
  • There is a reiteration of the need to consider planar graphs, noting that not all graphs fall into this category.

Areas of Agreement / Disagreement

Participants express differing views on the nature of graph drawability and the implications of edge crossings, indicating that multiple competing perspectives remain without a consensus.

Contextual Notes

The discussion does not resolve the assumptions regarding edge crossings or the definitions of planar versus non-planar graphs, leaving these aspects open for further exploration.

paizhaulski
Messages
2
Reaction score
0
Are there any theorems that say something formal about the fact that any graph is drawable on a 2D surface, and can be mapped to a 2D array of pixels if the pixels are infinitely small?
 
Physics news on Phys.org
This looks trivial, and easy to prove yourself if you really want to. Assuming edges can cross each other, of course.
 
When you say that, it implies that there is some way to distinguish between edges that cross at a point which is not a vertex and edges that meet at a vertex. In general, there will be lines crossing with no vertex there.
 
  • Like
Likes   Reactions: paizhaulski
paizhaulski said:
Are there any theorems that say something formal about the fact that any graph is drawable on a 2D surface, and can be mapped to a 2D array of pixels if the pixels are infinitely small?

Look at material about "planar graphs". Not all graphs are planar graphs.
 

Similar threads

Undergrad Adding 'z' to 2D graph equation
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Can 2D Vector Subspaces Form 3D Surfaces and How to Find Their Intersection?
  • · Replies 16 ·
Replies
16
Views
2K
Undergrad What is Riemann's approach to classifying 2d surfaces?
  • · Replies 6 ·
Replies
6
Views
3K
Python Help solving a geometrical matching issue with Graph Neural Networks
  • · Replies 1 ·
Replies
1
Views
3K
Undergrad Get geodesics & parallel transport on 2D surfaces (discrete timestep)
  • · Replies 12 ·
Replies
12
Views
3K
High School 2D Model of the Universe as an expanding ball
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad Did I figure-out z-translation of 2D-coordinates correctly?
  • · Replies 4 ·
Replies
4
Views
3K
Undergrad A Function for multiple 2D Gaussians
  • · Replies 8 ·
Replies
8
Views
2K
Undergrad Constructing dimensions out of a graph structure?
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Follow-up Einstein Definition of Simultaneity for Langevin Observers
  • · Replies 3 ·
Replies
3
Views
2K