regions (through critical lines) were performed in ArcGIS 
environment. 
2.3 Graph construction 
Towards the establishment of a network of connectivity within 
the given data set and the generated TIN, this approach 
identifies graph nodes as each one of the polygons aggregated 
from TIN triangles. 
To build up a graph of adjacencies it was necessary to access 
polygon and respective arc attributes to retrieve polygon 
adjacencies which, as we are using an ArcGIS environment, 
implied a combination of information spread basically over two 
lists: polygon component arcs list (information referring to area 
definition) and the arc adjacent polygons list (information 
referring to connectivity of arcs and contiguity of polygons). 
Figures 4 and 5 show the graphs obtained for the different 
classifications carried out, using 60° and 45° slope thresholds 
respectively. 
  
24842 A 
ss 
NET 
NS 490 180,7; 
z^ — 
191 160457 
SE 
  
  
  
  
Figure 4. Respective graph of adjacencies for the Public 
Records Office area (60? slope threshold). 
Graphs obtained are planar graphs as they can be drawn on the 
plane without any crossing edges and such that no two end- 
nodes coincide. According to one of the graph theory theorems 
(save the obvious exception of graphs containing loops or 
multiple edges), planar simple graphs (like those obtained) can 
always be drawn in such a way that all its edges are represented 
by straight lines, as was proved in 1936 by Wagner (Wilson, 
1996). Thus, graph in Figure 4 was redrawn in that way. 
In order to carry out the task of redrawing the graph using only 
straight lines, a slightly different arrangement of its nodes had 
to be considered and therefore the planimetric location of some 
of them actually changed. Nevertheless, their relative position 
to each other is absolutely the same (in other words, their 
topological relations were preserved) and hence the graph 
obtained is essentially the same as well, though with a slightly 
different configuration. More precisely, we shall say that the 
two graphs are isomorphic. 
We did not accomplish the same task for the graph in Figure 5 
as it is too complex. In addition to this, the reason for the 
straight lines drawing was just an attempt to point out an 
extremely important fact for us since we are interested in 
studying and analyzing topological relations between the spatial 
objects: although the planimetric location of some of the graph 
nodes changed, their relative position to each other was 
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004 
preserved. And that is what topology is all about, about the 
invariant properties of a map under deformation (Laurini and 
Thompson, 1992). This fact makes definitely clear the 
effectiveness of graphs in storing topological information of a 
given scene. 
  
       
   
  
     
BEL 
Legend N t. 
  
Levels of adjacency 
0. {1 ncde; 
2 
{AY 17 (26 modes) NV 
A 7 
(4) 2*9 (et vo / io 
(5 31^ (51 nodes) LE 
( 1 4* (9 nodes) 
  
Figure 5. Respective graph of adjacencies for the 
Public Records Office area (45° slope threshold) 
and its different levels of adjacencies. 
In Figure 5 different levels of adjacency are represented. 
Polygon 3 (highlighted on the right hand side of Figure 5) is the 
largest and the most connected //at one and therefore the one 
used as the Useful External Border (vd. Nardinocchi ef al’s 
definition for the UEB, 2003) with which the graph construction 
was started. Thus, assuming that polygon 3 is, in fact, the 
ground polygon, those levels of adjacency can also be seen as 
different levels of containment. 
3. DISCUSSION 
By observing different paths within the generated graphs, 
namely by trying to understand the geographical meaning of 
sequences of different levels of adjacency, and containment, 
between nodes (which represent polygonal regions generated 
from the original TIN facets) along graph paths, we concluded 
that different types of analyses will be possible to retrieve 
further geographical information. For instance, we may say that 
the polygon represented by the node in the tail of a graph path 
(representing the highest level of adjacency) is a candidate to be 
either a “hole” on the ground or “something” on the top of an 
urban entity, say, a building. 
To give an example of what kind of scene analysis might be 
possible to carry out once the whole process is automated, let us 
try to understand the meaning of a graph path in terms of urban 
scene, and for that, let us consider for instance the one 
highlighted in Figure 6 (a detail of the bottom left-hand corner 
of Figure 5). 
1050 
  
—