All Questions
Tagged with planar-graphs directed-graphs
11
questions
0
votes
0
answers
90
views
Given a directed graph, can you determine if it can be drawn as a planar graph?
Say a directed graph has loops and has nodes directed towards each other.
I would like to know if there is an algorithm for determining if the graph can be drawn as a planar graph.
- 185
2
votes
2
answers
231
views
Computing Longest Simple Path in a Particular Digraph
Let $D$ be a digraph as follows:
I want to compute a longest simple path of it.
For an acyclic digraph, there is a method I can run in Python that returns a longest path, but $D$ is not acyclic.
I ...
- 3,171
1
vote
0
answers
216
views
Number of loops in a type of directed multigraph
I am interested in finite directed multi-graphs with one connected component, where each vertex comes with exactly 1 edge pointing out from it, which can point to another vertex, or itself. So self-...
- 394
2
votes
1
answer
171
views
Maximum number of edges in a balanced graph with n points, without small cycles (say, of length 2, 3, 4)
Let's say we have $n$ points numbered from $1$ to $n$.
What is the maximum number of directed edges possible on a graph with these $n$ points:
without any cycle of length $\leq k$, for example ...
- 1,561
1
vote
0
answers
101
views
chromatic number in directed graphs
the chromatic number in directed graphs $χ_A$(D) is defined as the smallest integer such that there is a coloration without monochromatic directed cycles. it follows that if D is a planar graph, then:...
- 151
2
votes
0
answers
53
views
Dificulty to prove chromatic number of directed planar graphs
So I was reading this question and tried to prove it but I don't understand the statements that the answer and comments say since I don't what is a 2-dim sphere and can't understand why $D$ can be ...
- 53
3
votes
1
answer
196
views
Show that if $D$ is a planar directed graph without directed edges going in both ways, then $χA (D) ≤ 3$
I have stuck been with this problem.
I know that the chromatic number in a directe graph $χA (D)$ is defined as the smallest integer such that there is a coloration without monochromatic directed ...
- 141
0
votes
1
answer
88
views
Directed graph with $15$ edges and $16$ nodes
Does this kind of graph have a name other than it is an directed graph?
Does it have a property or characteristics? Visually I see $15$ edges and $16$ nodes. I want to learn more about graphs, but ...
user366820
1
vote
0
answers
542
views
Say that a tournament T has 2-property, if for every distinct vertices u, w ∈ V ( T ), T has a (directed) u,w-path of length exactly 2.
Say that a tournament T has 2-property, if for every distinct vertices $u,w \in V(T)$, T has a (directed) u,w-path of length exactly 2. (In particular, if T has 2-property, then every vertex of T is a ...
3
votes
2
answers
171
views
Relationship between graphs describing horizontal and vertical cell network
In the July 1997 Scientific American issue, Ian Stewart wrote a piece about squared squares (see here):
He uses vertical walls (in bold) as nodes and the squares as edges from which he can build up a ...
- 289
2
votes
2
answers
261
views
Planarity of a “cell graph”
I am working on a very simple model for biological cells arranged in a tissue, which can be expressed with directed acyclic graphs. In this model, which is explained in detail below, vertices are ...
- 289