Any nonplanar cave graphs?

Techniques, equipment and issues. Also visit the NSS Survey & Cartography Section.

Moderator: Moderators

Any nonplanar cave graphs?

Postby Bob Thrun » Jul 15, 2012 12:08 am

Rich Breisch says, on page 124 of his book Lost in a Cave, "As far as I know, no cave cartographer has ever shown that any natural cave is nonplanar." He means nonplanar in the graph theory sense. The classic maze caves, such as Anvil, Hamilton, and MarkTwain, are obviously planar. So are the linear caves whose maps I have looked at. Does anybody know of a cave whose map is nonplanar? Has anybody tested caves for planarity?
Bob Thrun
NSS Hall Of Fame Poster
 
Posts: 322
Joined: Jul 18, 2006 12:50 pm
  

Re: Any nonplanar cave graphs?

Postby John Lovaas » Jul 15, 2012 11:04 am

Hi Bob-

I have a few questions, based on the author's (context-free)quote:

"As far as I know, no cave cartographer has ever shown that any natural cave is nonplanar."

- are there any cave cartographers claiming that a natural cave is nonplanar?
- are there any cave cartographers looking at 'planararity/nonplanarity' in caves?

Is there a published paper on planar/nonplanar caves? The only uses of planar and nonplanar at speleogenesis info is in reference to types of dolomite. There's nothing in my copy of Speleogenesis, and the search terms yield nothing at the Karst Information Portal.

And, as a cave cartographer, I've never thought about it in my life. Of course, I have no idea how the terms are being used in this context. The only Google results for nonplanar(or non-planar)+cave(and not CAVE) are from this discussion thread.

Not that Google is an end in itself, but that may be another clue as to why no cave cartographer has shown that any natural cave is nonplanar.

The only definition of non-planar I could find is this:

"...Non-planar refers generally to a polygon where all points do not reside in the same plane and can occur only with polygons using more than three points..."

With the exception of a few shelter caves I've surveyed, and some maze type caves, Non-planar describes every cave I've ever surveyed, and every cave map I've ever produced.

I presume the author looked at cave maps that include cross sections and profiles, or, at least elevations assigned along the plan view- and looked at cave maps from around the world. Some large maze caves may have been formed by very slow moving groundwater, so the hydrologic gradient will clearly help define the cave. The hydrologic gradient would be fairly planar, I bet- at least in a very small geographic area.

Lechugilla- and other hypogenic caves- not very planar. Tectonic caves- not necessarily planar. Flank margin caves- not necessarily planar.

How does the author define planar and non-planar caves?
imbecile sheepherder.
User avatar
John Lovaas
NSS Hall Of Fame Poster
 
Posts: 590
Joined: Sep 6, 2005 9:10 am
Location: Woodstock, Illinois
  

Re: Any nonplanar cave graphs?

Postby Bob Thrun » Jul 15, 2012 3:16 pm

Rich Breisch's book is a combination of a search-and-rescue manual and a graph theory textbook. The term planar is used in a graph theory sense. Graph theory is one of the simplest branches of mathematics with the most abstract notation. A graph consists of edges and vertices (or arcs and nodes, or lines and junctions; the terms are equivalent). The edges are connected only at the vertices. Edges may cross without being connected. A cave map is a graph that shows passages (edges) and junctions (vertices). The edges may be stretched, moved, and curved. If the graph can be flattened so that it lays in a plane without any edges crossing, then the graph is planar. An easily described example of a nonplanar graph consists of five vertices, each vertex being connect to all the other vertices. In fact, this is the smallest number of vertices that can make up a nonplanar graph.

Does anyone have a computer program to test for planarity?
Bob Thrun
NSS Hall Of Fame Poster
 
Posts: 322
Joined: Jul 18, 2006 12:50 pm
  

Re: Any nonplanar cave graphs?

Postby John Lovaas » Jul 15, 2012 8:00 pm

Bob Thrun wrote:Graph theory is one of the simplest branches of mathematics with the most abstract notation.


So simple, I've never heard of it ;-)

Bob Thrun wrote:A graph consists of edges and vertices (or arcs and nodes, or lines and junctions; the terms are equivalent).


Does this graph have 2 or 3 axes?

Bob Thrun wrote:A cave map is a graph that shows passages (edges) and junctions (vertices). The edges may be stretched, moved, and curved.


Wouldn't the stretching, moving, and curving of the edges change the length of the edges? Wouldn't that be manipulating data to fit a model?

And what about flank margin caves? How would the author define large rooms with pillars as edges and vertices? Wouldn't that be a function of the quality of the data he is looking at, and the survey standard that the survey crew followed? And did the cartographer utilize all the data the survey team collected, or did the cartographer generalize some the the data?

Bob Thrun wrote:If the graph can be flattened so that it lays in a plane without any edges crossing, then the graph is planar.


That would define some caves, but clearly not all. Passages at different elevations can intersect and briefly connect- and much of the definition of how the passages connect and intersect depends on how motivated the surveyors are.

Bob Thrun wrote:An easily described example of a nonplanar graph consists of five vertices, each vertex being connect to all the other vertices.


If you are plotting the five vertices in 2 dimensions, wouldn't that define a splay shot of a room- albeit with a couple of extra shots?

Still grappling with the original quote: ""As far as I know, no cave cartographer has ever shown that any natural cave is nonplanar." I'm pretty sure that's because no one has ever bothered- otherwise there'd be one published paper on the subject somewhere! Someone please send me a link...

Every definition of nonplanar I've found today(including the mathematical ones) would apply to many surveys and maps of many caves. If by 'cave map' the author means a plan view lacking any elevation data- sure, that's planar- and, without parsing through the survey data, and the quality of the survey itself, a potentially inaccurate representation of a three-dimensional space.
imbecile sheepherder.
User avatar
John Lovaas
NSS Hall Of Fame Poster
 
Posts: 590
Joined: Sep 6, 2005 9:10 am
Location: Woodstock, Illinois
  

Re: Any nonplanar cave graphs?

Postby Bob Thrun » Jul 15, 2012 10:41 pm

Graph theory is about connectivity. It is not about spatial geometry, and is not about plots that show data values. I did a Google search for graph theory. I did not find a good introductory explanation in four pages of search results. Wikipedia tells what graph theory is good for, without explaining graph theory. The best I found is a Google project http://code.google.com/p/graphbook/ A reference on the first page of search results, http://diestel-graph-theory.com/ leads to a book that is a good example of incomprehensible notation. Rich Breisch's book is a better textbook than either of the two references I found.

Take a cave map. Keep all the passage junctions intact. Stretch the passages. Move them out from underneath each other. If you can do that and lay the "map" flat without any passages crossing, then the cave pattern is a planar graph.

I am copying a page from a graph theory textbook. Any nonplanar graph must have one of the two graphs shown as a subgraph. It is impossible to rearrange them so no edges cross.

Image
Bob Thrun
NSS Hall Of Fame Poster
 
Posts: 322
Joined: Jul 18, 2006 12:50 pm
  

Re: Any nonplanar cave graphs?

Postby Bob Thrun » Jul 16, 2012 2:20 am

I found a simple explanation of planar graphs:
http://www.personal.kent.edu/~rmuhamma/ ... narity.htm
Bob Thrun
NSS Hall Of Fame Poster
 
Posts: 322
Joined: Jul 18, 2006 12:50 pm
  

Re: Any nonplanar cave graphs?

Postby John Lovaas » Jul 16, 2012 10:27 am

Yes- the sources you've cited are familiar to me. Could you provide one real world application for graph theory, outside of grant generation and keeping mathematicians occupied?

My concerns with any map for SAR purposes is its accuracy and detail. If the humans on scene for a SAR situation can't interpret a cave map(or worse, interpret an inaccurate or incomplete cave map), how is feeding that map- or the original survey data- into a mathematical model somehow going to make it better? Wouldn't that be a case of garbage in, garbage out?
imbecile sheepherder.
User avatar
John Lovaas
NSS Hall Of Fame Poster
 
Posts: 590
Joined: Sep 6, 2005 9:10 am
Location: Woodstock, Illinois
  

Re: Any nonplanar cave graphs?

Postby Spike » Jul 17, 2012 10:23 am

So if I get this right a braided rope with vertices at each end would be non-planer as you cannot stretch a connecting line out without a strand crossing another strand. I think there is one series near Best Way Down in Mammoth that may fit. Also the old schematics of FSBs and how they tie together is a planer graph showing the connectivity of the surveys on single sheets. However they would often get complex enough that a second graph would be needed to show everything. It seems the nature of the cave and the mazes forced the creator to use another "layer" to keep the lines from crossing. This may be an empirical test to the theory.
User avatar
Spike
Prolific Poster
 
Posts: 134
Joined: Dec 23, 2005 3:25 pm
Location: Central MO
  

Re: Any nonplanar cave graphs?

Postby Bob Thrun » Jul 17, 2012 8:34 pm

Spike wrote:So if I get this right a braided rope with vertices at each end would be non-planer as you cannot stretch a connecting line out without a strand crossing another strand.

Actually, no. The braiding can be rearranged to make a planar graph. Here is an excerpt from the Ashley Book of Knots that shows how to do the braiding.

Image
Bob Thrun
NSS Hall Of Fame Poster
 
Posts: 322
Joined: Jul 18, 2006 12:50 pm
  


Return to Survey and Cartography Forum

Who is online

Users browsing this forum: No registered users