Props to Corsair

Posted on by
Reply

Just wanted to say thank you publicly to Corsair. The case for my computer ‘charisma‘ is a Corsair Carbide 100R Silent Edition Mid-Tower ATX Case. I really love this case and in fact I have two of them.

Anyway I had a problem where one of the feet snapped off and I couldn’t find spares for sale anywhere on the internet. I applied for a replacement of the feet through the Corsair warranty process, which was comprehensive but relatively painless, and I am pleased to report that my new replacement feet arrived today.

I am a happy customer!

Can a Directed Acyclic Graph always be put into the plane?

Posted on by
Reply

ChatGPT 4

User:

can a Directed Acyclic Graph always be put into the plane?

ChatGPT:

A Directed Acyclic Graph (DAG) can usually be drawn in the plane, but whether it can be drawn without any edges crossing (i.e., as a planar graph) depends on the specific structure of the DAG.

Planarity of a Graph:

A graph is considered planar if it can be embedded in the plane without any of its edges crossing each other. Not all graphs are planar. The planarity of a graph is generally tested using Kuratowski’s Theorem, which states that a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of either the complete graph K5 (five vertices each connected to every other vertex) or the complete bipartite graph K3,3 (two sets of three vertices with every vertex of the first set connected to every vertex of the second set).

DAGs and Planarity:

  • Acyclicity: A DAG, by definition, does not contain any cycles. This property alone does not guarantee planarity, but it does simplify the analysis since any subgraph involving cycles can be ignored when considering potential K5 or K3,3 configurations.
  • Structure and Complexity: The more complex the connectivity of the DAG (especially in terms of vertex connectivity and the number of edges relative to the number of vertices), the higher the chance that it could contain a non-planar configuration. A simple DAG with a tree-like structure, where each node has a few successors, is likely planar. However, as the number of edges and vertices increases, and especially if the graph forms dense interconnections between nodes, it could potentially include subdivisions of K3,3, making it non-planar.

To determine whether a specific DAG is planar, one would typically either:

  1. Look for subdivisions of K5 or K3,3 directly,
  2. Use algorithmic tools that implement planarity testing algorithms (such as the ones based on path addition or cutting algorithms).

Therefore, while many DAGs can indeed be drawn in the plane without crossing edges, it’s not universally true for all DAGs; the specific structure and connectivity must be considered.