Friday, December 26, 2014

A Review of Geometric Features and Visual Models for Radial Graph Presentation

This evening, I've been endeavoring to develop something of an idea as to how CLIM may be applied for drawing hyperbolic graphics onto CLIM panes -- focusing on McCLIM,  for such application, namely as with regards to the (MCi) fork of the original McCLIM codebase.  Although this initial study would be non-trivial, namely to my own limited academic knowledge of mathematical systems, but it's my hope that I may be able to trudge my way through this study, to develop something of an idea for a functional application of existing theory about hyperbolic graphs -- if not the broader algebraic topology -- namely towards a design of a new graphing component for McCLIM.

Reading [KobourovS2005], this evening, the authors denote two popular approaches for mapping a graph in the hyperbolic space onto the Euclidean plane:

  • Poincaré Disk Model
  • Beltrami-Klein Projections.

There are two additional approaches denoted by [ParksH]

  • Poincaré Half-Plane Model
  • Hyperboloid
This article, as a short collection of notes, will presently focus on the presentation in [ParksH]

  • Beltrami-Klein Projections
    • Named after the work of Eugenio Beltrami and Felix Klein (ca. 1870)
    • Euclidean space is constrained by a disk, for purpose of the projection
    • Points are defined within the circumference of the disk
    • Lines are presented as chords between points
      • For points A, B not on the circumference of the disk, the geometric extension of each of A and B to the circumference of the disk -- respectively, to points P, Q -- may be required for some calculations -- such as to calculate the projected distance between points A and B:
        • d(A,B) = 1/2 |log (AP*BQ) / (BP * AQ)|
      • For a A  situated on the circumference of the disk, A is denoted as an ideal point
    • The pole C for two points A, B, is the point on the Euclidean plane at which the lines defined as tangent to each of A and B meet in an intersection. C, of course, is not within the space of the disk
    • Concept of parallelism: Lines are parallel if they do not intersect within the area of the disk
    • Concept of perpendicularity: 
      • For line M being a diameter of the disk, N is perpendicular to M  -- in the hyperbolic projection -- if N is perpendicular to M in a a sense of the Euclidean coordinate space
      • For lines M and N not being a diameter of the disk: N is perpendicular to M, only if the geometric extension of N beyond the area of the disk would intersect the pole of M.
    • Angular measure: TBD
  • Poincaré Disk Model
    • Named after the work of Henri Poincaré (ca. 1880)
    • Likewise, Euclidean space is constrained by a disk, for purpose of the projection 
    • Likewise, points are defined within the circumference of the disk -- excluding the circumference or boundary of the disk. See also: [TernesM] 
    • For a circle -- as a geometric object -- defined within the hyperbolic projection, the circle has essentially two functional center points -- one for the circle in the Euclidean space, and one for the circle in the hyperbolic space, as projected onto the Euclidean space. See also: [TernesM], which the following sub-points are in reference to
      •  The midpoint of a line likewise has two coordinates -- one in the Euclidean space, and one in the projected hyperbolic space
      • The definition of an angular bisector must also be calculated for the characteristics of the projection
    • Two types of line, for points A, B:
      • A diameter of the disk, passing through points A, B
      • An arc passing through points A, B and ending as orthogonal to the circumference of the disk (see also: [VenemaG] p. 97, ch. 14) 
    • Concept of parallelism (arcs) : That the arcs M, N do not intersect at any point within the disk
    • Concept of perpendicularity: That two lines M, N meet orthogonally i..e at a right angle (See also: Angular measure)
      • A relatively easy matter to calculate, computationally, for two lines that are diameters in the Poincaré Disk projection
      • Less relatively easy to  calculate, if either or both of M and N is an arc
    • to calculate the projected distance between points A and B, with ideal points P and Q:
      • d(A,B) = |log (AP*BQ) / (BP * AQ)|
      • This is expressed in [VenemaG]  (p. 97, ch. 14) as follows:
        • d(A,B) = |ln(AB, PQ)|
    • Angular measure: "To measure the angle between two lines in a Poincaré Disk, you measure the Euclidean angle between their tangent lines."
      • TBD: Some ambiguity as to what the term tangent line may mean, in that definition. In any interpretation, that definition would be constrained only ti arc type lines within the disk
        • If the term refers to a line draw tangent to a point on the circumference of the disk,  and external to the circumference, but for any line AB, there would be two tangent lines in that interpretation. Those lines, of course, would be parallel if AB describes a diameter of the disk.
        • If the term refers to a line drawn tangent to each endpoint of an arc -- namely, at the points where the arc meets the circumference of the disk, ortogonally -- then for any line AB, there would be only two such tangent lines, both meeting on the Euclidean plane, at a point within the circumference of the disk
        • In either interpretation, there would be -- respectively -- four or two individual tangent lines for each arc. It would then be effectively impossible to measure the angle between tangent lines for two intersecting arcs
        • In a third interpretation: The term tangent line, in that application -- and namely, for an arc type line -- might refer to a line drawn tangent to the arc, at the point of the intersection. For a non-arc type line, the line itself might be used for the determination of angle, at the intersection. This is probably the correct interpretation of the term. See also: [WolframP]
    • Limit Rays: Arcs that meet at a common point on the circumference of the disk [WolframP]
  • The author describes a method for projecting a Beltrami-Klein Projection onto the Poincaré Disk Model

Of course, the hyperbolic trigonometric functions may have some applications in a graphing model for information visualization. See also: [KobourovS2005][KobourovS2012]

For a more in-depth analysis of the geometry of the hyperbolic space in the Poincaré Disk projection, see also: [SchutzA]

The qualities of the abstract geometric spaces of these projections would certainly make for a lengthy study, to the student of mathematics. Concerning a question of how these projections may be applied for information visualization, there are some many illustrations provided in [KobourovS2005] and [KobourovS2012]. Perhaps it may be well to consider some additional models, furthermore -- not limiting the discussion to the set of known hyperbolic projections. 

Certainly, there is a significant variety of information visualization models  defined in the information sciences. [HermanI] Particularly, either of the Cone Tree / Relative Disk Tree (RDT) projection models proposed in [JeongC] or the model proposed in [MelanconG] might serve to define a visually appealing graph with a minimum of spatial compaction, in a visual model for a directed acyclic graph (DAG). 

Towards development of an ontology model, such as may be suitable for construction of a DAG view: In an application of SKOS,  as within an OWL ontology model, it may be advisable to ensure that every object property defined in the ontology will be a subclass -- whether directly or indirectly -- of exactly one of the object propertiesskos:broader or skos:narrower, With that level of consistency in an ontology, and given any single individual instance M1 within the ontology, it would be possible to define a simple algorithm for computing the descendants of M1 by following the graph of skos:narrower relations -- directly, or as the compliment of skos:broader - for all property expressions within a specific instance of applying the graphing algorithm. to the ontology, selecting each property of which M1 would be a subject, then subsequently taking each object of the relation as the subject for a subtree, for any number of object properties selected in any one instance of applying the graphing algorithm -- the graphing instance being constrained, for purpose of brevity, constrained to any number of generational iterations of the algorithm.

Of course, although the graph display procedures might be the most time-consuming features to design for an ontology visualization system -- as to display any single structure of any single graph of individual instances and their object property relations, within an OWL ontology -- however, a graph itself may not serve to convey all of the information presented in an ontology. 

In at least, a complimentary table/page view model might be applied, as to create a focused view for display of ontologically structured information for any single individual instance within the ontology. The table/page view might be applied, moreover, as to allow for a convenient editing onto the set of ontology properties defined to any single individual instance. 

Considering the effective depth of complexity that this article has now arrived to, this article will conclude at the simple remark: "TO DO: Study"

Some additional works were discovered, during the research for this article, namely as with regards to hyperbolic projections onto the Euclidean space. [ChepoiV][BowditchB]. 

[KobourovS2005] Kobourov, Stephen G and  Kevin Wampler. Non-Euclidean Spring Embedders  (2005)
[ParksH] Parks, Hal. The Poincare Disk Model and The Klein—Beltrami Model.
[VenemaG] Venema, Gerard A. Exploring Advanced Euclidean Geometry with Geometer's Sketchpad. Archived
[WolframP] Wolfram MathWorld. Poincaré Hyperbolic Disk
[SchutzA] Schutz, Amy. Hyperbolic Functions.
[TernesM] Ternes, Megan. Tangent Circles in the Hyperbolic Disk
[KobourovS2012] Kobourov, Stephen G. Spring Embedders and Force Directed Graph Drawing Algorithms (2012)
[HermanI] Herman, Ivan , Guy Melançon , and M. Scott Marshall. Graph Visualization and Navigation in Information Visualization: a Survey
[JeongC] Jeong, Chang-Sung and Alex Pang. Reconfigurable disc trees for visualizing large hierarchical information space. See also: [Related]
[MelaonconG] Melançon G and I. Herman. Circular Drawings of Rooted Trees
[ChepoiV] Chepoi, Victor et al. Diameters, Centers, and Approximating Trees of δ-Hyperbolic Geodesic Spaces and Graphs
[BowditchB] Bowditch, B. H. Relatively Hyperbolic Groups