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

ChatGPT 4


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


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.

Quality capacitors: Nichicon

Note to self: I was watching EEVblog #378 – Dumpster Diving Teardown Repair and EEVblog #763 – Dumpster Plasma TV Bad Cap Repair and Dave Jones says Nichicon make high quality capacitors. Apparently Panasonic, Nippon Chemi-Con, Rubycon, and Cornell Dubilier are also good.

Soldering tips from Dave Jones

In his video EEVblog #186 – Soldering Tutorial Part 3 – Surface Mount Dave Jones says to use soldering iron temperature of 300°C to 350°C. He set his hot air gun at 350°C.

He also recommends 4x or 6x magnifications for 0402 SMD and recommends not to use them (or smaller) unless you have to because they can increase manufacturing costs due to being small and fiddly and requiring magnification during soldering. The smaller components can affect yield.

For solder he recommends 0.46mm solder (recommended Multicore brand). And flux. Always use flux.

Also he’s on the record as preferring a chisel tip. In this video he also demoed a thing called a “well tip“, which I have never seen or used before. Apparently good for drag soldering?

While I was researching this post I came across the Hakko Product Lineup, they have some nice looking kit!

p.s. in EEVblog #180 – Soldering Tutorial Part 1 – Tools Dave suggests solder in this order:

  1. 62sn/36pb/2ag
  2. 63sn/37pb
  3. 60sn/40pb

The first one with silver in it can be good for some SMT devices. The second one has a more stable melting point. The third is tried and tested but has variable range of melting points.

Note: sn = tin; pb = lead; ag = silver.